Lecturer: Dr A.C. Norman (acn1@cl.cam.ac.uk)
Introduction: what calculations are feasible?
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.
Infeasible problems.
Recommended books:
Cormen, T.H., Leiserson, C.E. & Rivest, R.L. (1990). Introduction to Algorithms. McGraw-Hill.
Knuth, D.E. (1981). The Art of Computer Programming, vol. II. Addison-Wesley.