Week 1: Turing machines, motivation, simple examples of
        things that TMs can do
Week 2: More examples of TMs recognizing langauages, the
        idea that TMs capture the notion of an algorithm,
        the Church--Turing thesis, a proof of the 
        non-existence of a hello-world tester.
Week 3: Codes for TMs, diagonalization, a language not
        recognizable by TMs, the `acceptance' language
        that is not decidable by TMs. Proving other 
        languages undecidable.
Week 4: Rice's theorem and the undecidability of the 
        PCP.
Week 5: Polynomial time decidable languages, examples.
        An argument that TMs simulate RAM programs with
        polynomial overhead.
Week 6: Languages in P vs Langauges not in P: avoiding
        brute force. The class NP of poly-time verifiable
        languages. The P vs NP question. Poly-time
        reducibility and the definition of NP-complete.
Week 7: Non-deterministic Turing machines. Characterization
        of NP in terms of non-deterministic TMs.  Cook's theorem. 
Week 8: Proof of Cook's theorem completed. Review and Midterm.
Week 9: Space complexity and Savitch's Theorem; PSPACE and
        illustrative problems.
Week 10: PSPACE-complete problems: Truth of quantified boolean
        formulae, and the generalized geography game.
Week 11:Time and Space hierarchy Theorems.
Week 12: Testing polynomial identities, read-once branching programs,
        RP and BPP.
Week 13: RP, co-RP, the intersection of RP and co-RP, BPP, Interactive
         proofs.
Week 14: #SAT is contained in IP.
Week 15: PSPACE is contained in IP, Review.