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!
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.
- Notes: Introduction - Practicalities - Chapter 1 - Chapter 2 - Chapter 3 - Chapter 4 (and that's the lot!)
- Exercises: Sheet 1 - Sheet 2 - Sheet 3 (there is no Sheet 4 - exercises for Chapter 4 are on Sheet 3 - but there will be a sheet of revision exercises)
- Solutions: Sheet 1
- Past Exam Paper: 2013-14
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 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.