|
Date
|
Subject
|
Resources
|
|
Week 1, Jan 8-12
|
Course introduction and background. Review of notation. Introduction to deterministic finite automata (DFA)
|
|
|
Week 2, Jan 15-19
|
DFA's continued. Introduction to non-determinism and non-deterministic finite automata (NFA)
|
|
|
Week 3, Jan 23-26
|
NFA's continued. Equivalence of DFAs and NFAs.
|
|
|
Week 4, Jan 29-Feb 2
|
Closure properties of regular languages. Regular expressions. Pumping lemma for regular languages.
|
|
|
Week 5, Feb 6-9
|
Introduction to context-free grammars (CFG)
|
|
|
Week 6, Feb 13-16
|
Introduction to push-down automata (PDA). Pumping lemma for CFGs. Midterm during Thursday's tutorial session (Covering all materials from Weeks 1-5).
|
|
|
Feb 19-23
|
Reading week. No class.
|
|
|
Week 7, Feb 26-Mar 1
|
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-22
|
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? (NO LECTURE ON FRIDAY 29th).
|
|
|
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
|
|