CS 475: Lecture Schedule
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.
Schedule
- 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