next up previous contents
Next: Computer Graphics and Image Up: Easter Term 2002: Part Previous: Business Studies   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 book


Papadimitriou, Ch.H. (1994). Computational Complexity. Addison-Wesley.



next up previous contents
Next: Computer Graphics and Image Up: Easter Term 2002: Part Previous: Business Studies   Contents
Christine Northeast
Tue Sep 4 09:34:31 BST 2001