Computational Complexity Theory
These are presentations for an undergraduate Computational Complexity Theory course.
The same could be found at http://computational.complexity.googlepages.com/home
They are in a powerpoint 2007 format --- if you don't have it installed, you can find a viewer by Microsoft here.
You can find handouts versions as wellas slides in 
PDF
format.
They are based on previous versions, which you can find here.
Presentations:
Introduction (pdf:
handouts, slides)
Turing Machines; (pdf:
handouts, slides)
NP-completeness; (pdf:
handouts, slides)
Space Complexity (pdf:
handouts, slides)
pdf NL
closed under complement
Approximation Problem; (pdf:
handouts, slides)
PCP; (pdf:
handouts) Notes
for the PCP and Hardness of Approximation
PH and BPP; (pdf:
handouts)
Random
Walks (pdf
file)
_______________________________________________________