What is Complexity Theory?
Syllabus
Problems
Algorithms
Notes .pdf file, Contains
chapter on NP-completeness
Important Links
NP-complete problem list
Complexity Classes
Sanjeev Arora's Notes
Luca Trevisan's Notes
To read the above lecture notes, you will need to install
Ghostscript then Ghostview on your machine, they are available
for free download
Schedule:
Problems. Chapter 2. 1/27
Problems Chapter 3. 2/5
Problems Chapter 4 problems 2/12
Problems SAT problem 2/19
Problems Chapter 5 problems 2/19
Exam 1. Due: March 2
Term paper topic due March 23
10-Problem set: Due 3/30
Final Exam : due 4/27
Term Paper: due 4/24