Lecturer: Dr A.C. Norman (acn1@cl.cam.ac.uk)
No. of lectures: 12
Prerequisite courses: Data Structures and Algorithms, Computation Theory
The course will include the following topics:
Introduction: what calculations are feasible?
Infeasible problems.
How to discuss complexity without becoming tied to one particular
sort of computer.
Polynomial time (P-space).
Verifying solutions in P-time; the class NP.
Cooke's Theorem (3-SAT is NP-complete).
Other NP complete problems: Clique.
Hamiltonian Circuit, Travelling Salesman.
Approximation and NP problems.
Integer multiplication as a fundamental computational task.
The classical algorithm. Karatsuba.
An evaluation-interpolation strategy.
Fast Fourier Transforms.
Reduction between multiplication and division. Square roots etc.
Recommended books:
Cormen, T.H., Leiserson, C.E. & Rivest, R.L. (1990). Introduction to Algorithms. McGraw-Hill.
Knuth, D.E. (1998). The Art of Computer Programming, vol. II. Addison-Wesley (3rd ed.).