Comp 330 - Theory of Computation - Fall 2023

This is the archived website of the Comp 330 - Theory of Computation class which was taught at McGill in the Fall 2023 semester.1 It contains some logistical information as well as lecture notes and other class material. Assignments can be found at the very end of this webpage. In case you are curious, I also wrote a blog post about my experience teaching this course which you can find here.

Instructors: Cesare Spinoso-Di Piano and Claude Crépeau
TAs: Hillary Tao, Yuyan Chen, Yao Chen, Leo Shi, Ben Cheung, Morgan Chapados
Lecture time: Tuesdays and Thursdays, 8:35 AM to 9:55 AM
Class location: Stewart Biology S1/4

Schedule, lectures notes and supplementary material

Lecture Date Topic Lecture Video Lecture Notes Extra Notes
1 Aug 31 Intro, Maths review No video. See Tutorial Series for related content. Notes Supplementary: Partial orders and the principle of induction
2 Sept 5 Formal language theory Recording Notes  
3 Sept 7 Deterministic finite automata (DFA) Recording + Extra recordings here, here and here Notes Supplementary: Completing induction argument
4 Sept 12 Minimal DFA, Non-deterministic finite automata (NFA) Recording Notes  
5 Sept 14 NFA=DFA, NFA+\(\varepsilon\) Recording Notes Supplementary: Formal proof of equivalence
6 Sept 19 Closure properties of regular languages Recording Notes  
7 Sept 21 Regular expressions Recording (Part 1 of 6) - See the Youtube playlist for the other parts Notes Supplementary: Expanded discussion of conversion algorithm
8 Sept 26 DFA minimization Recording Notes  
9 Sept 28 The Myhill-Nerode theorem Recording Notes  
10 Oct 3 Non-regular languages, The Pumping lemma M-N to show non-regularity + Non-regular language intuitions Notes  
11 Oct 5 Proving languages are not regular Recording Notes  
12 Oct 10 Midterm review No video. Notes  
- Oct 12 Midterm exam      
13 Oct 17 Intro to context-free languages (CFLs) and the Chomsky hierarchy Recording Notes  
14 Oct 19 CFLs: Proof of correctness and closure properties Recording Notes Supplementary: Completing induction argument
15 Oct 24 CFLs: Ambiguity and CFL-related decision procedures No video. Notes Supplementary: Formal definitions
16 Oct 26 Pushdown automata Recording Notes  
17 Oct 31 Pumping lemma for CFLs Recording Notes  
18 Nov 5 Turing machines (TMs) Recording Notes Supplementary: Completing TM definition
19 Nov 7 The halting problem No video. Notes Guest lecture by Prof. Prakash Panangaden
20 Nov 12 Intro to reductions Recording Notes Supplementary: \(HP \leq_m AP\) argument
21 Nov 14 More reductions! Recording Notes  
22 Nov 19 Characterizing undecidability Recording Notes Supplementary: Extra proofs
23 Nov 21 Rice’s theorem Recording + Clarification on notation Notes  
24 Nov 26 Undecidable problems about CFLs Recordings (Part 1 of 9) Notes  
25 Nov 28 The Post correspondence problem Recording Notes  
26 Dec 5 Review of reductions and Turing reductions Recording - Consult notes at the same time. Notes  

Assignments



  1. In fact, the students did not have access to this website during the semester and instead used myCourses. However, I have decided to make most of the contents of the course publicly accessible via this webpage. ↩