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 SpinosoDi 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, Nondeterministic 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 MyhillNerode theorem  Recording  Notes  Â 
10  Oct 3  Nonregular languages, The Pumping lemma  MN to show nonregularity + Nonregular 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 contextfree 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 CFLrelated 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
 Assignment 1: Handout
 Assignment 2: Handout
 Assignment 3: Handout
 Assignment 4: Handout
 Assignment 5: Handout
 Assignment 6: Handout

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.Â ↩