Lecture Schedule

Date Subject Resources
Week 1, Sep 8-12 Course introduction and background. Review of notation. Introduction to deterministic finite automata (DFA)
Week 2, Sep 15-19 DFA's continued. Introduction to non-determinism and non-deterministic finite automata (NFA)
Week 3, Sep 23-26 NFA's continued. Equivalence of DFAs and NFAs.
Week 4, Sep 29-Oct 3. No lecture on Tuesday, Sept. 30th Closure properties of regular languages. Regular expressions. Pumping lemma for regular languages.
Week 5, Oct 6-10 Introduction to context-free grammars (CFG)
Week 6, Oct 13-17 Introduction to push-down automata (PDA). Pumping lemma for CFGs.
Week 7, Oct 20-24 Introduction to Turing machines (TM). TM examples. One hour Midterm Oct. 24th during Fridays's tutorial session (Covering all material from Weeks 1-5).
Week 8, Oct 27-31 The Church-Turing Thesis. Decidability and Decidable languages.
Nov 3-7 Reading week. No class.
  • N/A
Week 9, Nov 10-14 Universal Turing machines. The halting problem and other undecidable languages.
Week 10, Nov 17-21 Computational complexity and running time. Complexity classes P and NP.
Week 11, Nov 24-28 The class NP-Complete. The Cook-Levin Theorem and the million dollar question... does P=NP?
Week 12, Dec 1-5 The class NP-Hard. Probabilistic Turing machines and the class BPP. Quantum computers and the class BQP.
Week 13, Dec 9th Exam review