The schedule below lists the topic of each lecture, with links to relevant notes, slides, and lecture videos. "AC" refers to Automata and Computability by Dexter Kozen, while "ToC" refers to Theory of Computation by Dexter Kozen. **All future lecture topics are subject to change, but exam dates are not.**

**Videos of past lectures this semester are available here.**

- Tues Aug 22
- Administrivia, and Regular Languages/Expressions

**Material:**Lectures 1, 2 of AC

[slides, scribbles, video] - Thurs Aug 24
- Finite Automata: Determinism, Nondeterminism, Alternation, and 2-way machines

**Material:**Lectures 3, 4, 5, 17, 18 of AC and Miscellaneous Exercises 59 and 61.

[notes, scribbles, video] **Homework 1 and WarmUp 1 released**- Tues Aug 29
- Automata constructions, closure properties, and Kleene's Theorem

**Material:**Lectures 6, 8, 9, 10 of AC.

[scribbles, video] - Thurs Aug 31
- Non regularity and Myhill-Nerode Theorem

**Material:**Lectures 11, 12, 15, 16 of AC.

[scribbles, video] **WarmUp 2 released**- Tues Sep 5
- Context-free Grammars and Languages

**Material:**Lectures 19, 20 of AC.

[scribbles, video] - Thurs Sep 7
- Pumping Lemma and non Context-free languages

**Material:**Lectures 21, 22 of AC.

[scribbles, video] **Homework 1 due. Homework 2 and WarmUp 3 released**- Tues Sep 12
- Pushdown Automata and Equivalence with CFGs
**Material:**Lecture 23, 24 of AC.

[scribbles, video] - Thurs Sep 14
- PDAs, CFLs, CNFs, GNFs, and CYK

**Material:**Lecture 25, 27 of AC.

[scribbles, video] **WarmUp 4 released**- Tues Sep 19
- Turing Machines and the Church-Turing thesis

**Material:**Lectures 28, 29, 30 of AC and notes.

[slides, video] - Thurs Sep 21
- Diagonalization, Undecidability and Reductions
**Material:**Lectures 31, 32, 33 of AC.

[scribbles, video] **Homework 2 due. Homework 3 released****Tues Sep 26****Midterm 1: 3:30pm to 4:45 (in class).**- Thurs Sep 28
- Hardness and Completeness, Rice's Theorem
**Material:**Lectures 33, 34 of AC.

[scribbles, video] **WarmUp 5 released**- Tues Oct 03
- Oracle Turing Machines and the Arithmetic Hierarchy
**Material:**Lectures 35, 36 of ToC, and Supplementary Lecture J of AC.

[scribbles, video] - Thurs Oct 05
- Time and Space Complexity Classes
**Material:**Lecture 2 of ToC.

[scribbles, video] **Homework 3 due. Homework 4 and WarmUp 6 released**- Tues Oct 10
- Savitch's Theorem
**Material:**Lecture 2 of ToC.

[scribbles, video] - Thurs Oct 12
- Hierarchy Theorems
**Material:**Lecture 3 of ToC.

[scribbles, video] **WarmUp 7 released**- Tues Oct 17
- NL
**Material:**Lectures 4, 5 of ToC

[scribbles, video] - Thurs Oct 19
- P and Circuit Value Problem
**No lecture. Watch posted video****Material:**Lecture 6 of ToC

[video (MAZE and NL-completeness), video] **Homework 4 due. Homework 5 released****Tues Oct 24****Midterm 2: 3:30pm to 4:45 (in class).**- Thurs Oct 26
- NP and the structure within: Ladner's Theorem
**Material:**Section 14.1 of Computational Complexity by Papadimitriou

[scribbles, video] **WarmUp 8 released**- Tues Oct 31
- NP and the structure within: Berman/Mahaney's Theorem
**No lecture. Watch posted video****Material:**Section 14.2 of Computational Complexity by Papadimitriou

[video] - Thurs Nov 02
- Alternation
**No lecture. Watch pre-recorded video****Material:**Lecture 7 of ToC

[video] **Homework 5 due. Homework 6 and WarmUp 9 released**- Tues Nov 07
- Polynomial Time Hierarchy
**No lecture. Watch posted video****Material:**Lectures 8, 9, 10 of ToC

[video] - Thurs Nov 09
- Parallel Complexity
**No lecture. Watch posted video****Material:**Lecture 11 of ToC

[video] - Tues Nov 14
- Recap: Alternation, Polynomial Time Hierarchy, and Parallel Complexity
**Material:**Lectures 7, 8, 9, 10, 11 of ToC

[scribbles, video] - Thurs Nov 16
- Relation of NC to Time-Space Classes
**Material:**Lecture 12 of ToC

[scribbles, video] **Homework 6 due.****Nov 18 - Nov 26****Thanksgiving Break**- Tues Nov 28
- Probabilistic Complexity
**Material:**Lecture 13 of ToC

[scribbles, video] - Thurs Nov 30
- BPP and the Polynomial Time Hierarchy
**Material:**Lecture 14 of ToC

[scribbles, video] **WarmUp 10 released**- Tues Dec 05
- Interactive Proofs
**Material:**Lecture 15 of ToC **Mon Dec 11****Final exam**, 1:30pm-4:30pm in 4035 CIF