next up previous contents
Next: Computation Theory Up: Lent Term 2003: Part Previous: Compiler Construction   Contents


Complexity Theory

Lecturer: Dr A. Dawar (ad260@cl.cam.ac.uk)

No. of lectures: 12

Prerequisite courses: Data Structures and Algorithms, Computation Theory

Aims

The aim of the course is to introduce the theory of computational complexity. The course will explain measures of the complexity of problems and of algorithms, based on time and space used on abstract models. Important complexity classes will be defined, and the notion of completeness established through a thorough study of NP-completeness. Applications to cryptographic protocols will be considered.

Lectures

Objectives

At the end of the course students should

Recommended books

Papadimitriou, Ch.H. (1994). Computational Complexity. Addison-Wesley.
Sipser, M. (1997). Introduction to the Theory of Computation. PWS.


next up previous contents
Next: Computation Theory Up: Lent Term 2003: Part Previous: Compiler Construction   Contents
Christine Northeast
Wed Sep 4 14:43:05 BST 2002