Lecture Schedule

Date Subject Resources
Week 1, Jan 7-11 Course introduction and background. Review of notation. Introduction to deterministic finite automata (DFA)
Week 2, Jan 14-18 DFA's continued. Introduction to non-determinism and non-deterministic finite automata (NFA)
Week 3, Jan 21-25 NFA's continued. Equivalence of DFAs and NFAs.
Week 4, Jan 28-Feb 1 Closure properties of regular languages. Regular expressions. Pumping lemma for regular languages.
Week 5, Feb 4-8 Introduction to context-free grammars (CFG)
Week 6, Feb 11-15 Introduction to push-down automata (PDA). Pumping lemma for CFGs.
Feb 18-22 Reading week. Aw yea! No class.
  • N/A
Week 7, Feb 25-Mar 1 Midterm Monday Feb 25 2019 9:30-10:20am in FNB 1200 and FNB 1250. Introduction to Turing machines (TM). TM examples.
Week 8, Mar 4-8 The Church-Turing Thesis. Decidability and Decidable languages.
Week 9, Mar 11-15 Universal Turing machines. The halting problem and other undecidable languages.
Week 10, Mar 18-24 Computational complexity and running time. Complexity classes P and NP.
Week 11, Mar 25-29 The class NP-Complete. The Cook-Levin Theorem and the million dollar question... does P=NP? (Note: No class on Friday!)
Week 12, Apr 1-5 The class NP-Hard. Probabilistic Turing machines and the class BPP. Quantum computers and the class BQP.
Week 13, Apr 8 Exam review