MATH43011/63011 Computation and Complexity (2019-20)This page contains information and all materials for the 2019-20 presentation of the course.
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!
All notes and exercises are provided here. Please let me know if you need them in a differentformat because of a disability.
- Notes: Introduction - Chapter 1 - Chapter 2
- Exercises: Sheet 1 - Sheet 2
- Solutions: Sheet 1
- Past Exam Paper: 2014-15
- Coursework: First Coursework Test (due in Monday Week 5)
Video podcasts of lectures should be available, but these are intended as an additional resource and not a core part of the course or a substitute for attendance at lectures. The format of the lectures will be tailored to those present in the room, not to the recording, and I make no guarantees about the quality or reliability of the recordings. I recommend using the notes, rather than the podcasts, for catching up on missed lectures. If you do wish to use the recordings they can be found here.
Lecture TimesWe have 3 hours timetabled each week, to be used flexibly for lectures and tutorials....
- Thursday 09:00-11:00 (with a short break in roughly the middle) in Alan Turing G.205
- Friday 10:00-11:00 in Alan Turing G.209