• 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