MATH43012/63012 Computation and Complexity (2014-15 presentation)
Quite a lot of the mathematics you have studied so far involves using algorithms to solve computational problems. For example, you have probably used Euclid's algorithm to solve the problem of finding the greatest common divisor of two integers. In this course, we abstract a level further, and study the properties of problems and algorithms themselves. The kind of questions we ask are "is there an algorithm to solve every problem?" and "what problems can be solved by an efficient algorithm?".
Compared with most of mathematics, this area is in its infancy, and many important things remain unknown. The course will take you to the point where you understand the statement of one of the most important open questions in mathematics and computer science: the "P vs NP" problem, for which the Clay Mathematics Foundation is offering a $1,000,000 prize. And who knows, perhaps one day you will be the one to solve it!
SuitabilityThe course has minimal formal prerequisites, and is taken by quite a range of students:
- Third and fourth year MMath and MSc students are the main target audience and are very welcome.
- Mathematics PhD students are also welcome and can count the course towards their taught course requirements.
- Third year BSc Mathematics students may take the course with the permission of the Senior Tutor; it doesn't rely on any advanced courses but requires a degree of mathematical maturity.
- Students from other schools are welcome to attend on an informal (non-examined) basis; if you want to take the course for credit you should speak to me before registering.
Notes and exercises will also be given out in lectures, but are provided here in case you prefer to have an electronic copy. Please let me know if you need them in a different format because of a disability.
Lecture TimesThis is a little complicated, because of a training course I am taking myself during the semester. We have 4 hours timetabled each week, to be used flexibly for lectures and tutorials....
- Tuesday 11:00-12:00 in Roscoe 3.4
- Wednesday 11:00-12:00 in Devonshire G7 (before Easter) and University Place 5.211 (after Easter)
- Friday 09:00-11:00 (with a short break in the middle) in Alan Turing G.205
- Week 1: All slots
- Week 2: Tuesday and Wednesday only
- Week 3: All slots
- Week 4: Tuesday and Wednesday only
- Week 5: All slots
- Week 6: Tuesday and Friday only
- Week 7: All slots
- Week 8: All slots
- EASTER BREAK
- Week 9: Tuesday and Wednesday only
- Week 10: All slots
- Week 11: All slots
- Week 12: If all goes to plan, revision class on Tuesday, then no further lectures.