COMP 330 Winter 2021: Lecture Schedule
Prakash Panangaden
Week 1 Lecture 0 5 January
Lecture 1 7 January Introduction, basic maths A1 out
Week 2 Lecture 1 12 January Deterministic finite automata
Lecture 2 14 January Nondeterministic finite automata
Quiz 1 15-16 January Basic logic
Week 3 Lecture 1 19 January Regular expressions
Lecture 2 21 January Kleene’s theorem A1 due, A2 out
Week 4 Lecture 1 26 January The pumping lemma
Lecture 2 28 January The pumping lemma
Quiz 2 29-30 January DFA, NFA, regular expressions
Week 5 Lecture 1 2 February Minimization
Lecture 2 4 February The Myhill-Nerode theorem A2 due, A3 out
Week 6 Lecture 1 9 February Review
Lecture 2 11 February MIDTERM
Week 7 Lecture 1 16 February Context-free languages
Lecture 2 18 February Designing context-free languages A3 due, A4 out
Week 8 Lecture 1 23 February Pushdown automata
Lecture 2 25 February Designing pushdown automata
Quiz 3 26-27 February Context-free languages
Week 9 Lecture 1 9 March The pumping lemma for CFLs
Lecture 2 11 March Introduction to computability A4 due, A5 out
Week 10 Lecture 1 16 March Models of computation
Lecture 2 18 March Basic computability
Quiz 4 19-20 March Context-free pumping lemma
Week 11 Lecture 1 23 March Reductions
Lecture 2 25 March Reductions A5 due, A6 out
Week 12 Lecture 1 30 March Undecidable problems about CFG
Lecture 2 1 April The Post correspondence problem
Week 13 Lecture 1 6 April Undecidability of FOL
Lecture 2 8 April The recursion theorem A6 due
Quiz 5 9-10 April Reductions
Week 14 Lecture 1 13 April Review for the final
1