Weeks 1: Defining Computation via Circuits, Straight-Line Programs and its equivalence with circuits
Week 2: Universality of Circuits, the class SIZE{n,m}(s), Programs as strings & inputs to programs
Week 3: Existence of Hard Functions, Size Hierarchy Theorem
Week 4: Turing Machines, Turing Machines as Programs, RAM Model, Equivalence of Turing Machines and RAM Model
Week 5: Church-Turing Thesis, Universal Turing Machine, Undecidability, Halting Problem
Week 6: Defining time complexity for Turing Machines and RAM Models, relation between the two, the classes P and EXP
Week 7: Time Hierarchy Theorem, Non-Uniform Computation vs Uniform Computation
Week 8: 2-SAT vs 3-SAT, Determinant vs Permanent, Poly-time Reductions
Week 9: The class NP, NP-Completeness, Cook-Levin Theorem
Week 10: Defining Space Complexity, Space Hierarchy Theorem, Savitch's Theorem, the class PSPACE and its relation with NP
Week 11: The classes L and NL, log space reductions, NL completeness
Week 12: Randomised Computation, Efficient Randomised Algorithms for Polynomial Identity Testing, Bipartite Matching
Week 13: Modelling Randomised Computation, the classes BPP, RP, coRP, ZPP
Week 14: Upperbounds for BPP, Derandomisation and PRGs