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 all past lectures are available on a separate page. University login required.
- Tues Aug 29
- Administrivia, Cardinality, Diagonalization, Cantor-Schroeder-Bernstein Theorem
Material: lecture slides, cardinality notes, Pages 230-231 of AC
Background Reading: Lecture 2 of AC
- Thurs Aug 31
- Regular Languages: Deterministic, Nondeterministic, Universal, and 2-way machines
Material: Finite automata notes, Lectures 3,4,5,6,17, and 18 of AC and Miscellaneous Exercise 61 from AC.
- Homework 1 and Quiz 1 released
- Tues Sep 05
- Turing Machines and variants; Equivalence of deterministic and nondeterministic Turing machines
Material: Notes, Lectures 28, 29, and 30 of AC.
- Thurs Sep 07
- Undecidability and Reductions
Material: Lectures 31, 32, and 33 of AC.
- Quiz 2 released
- Tues Sep 12
- Reductions and Completeness
Material: Lectures 33 of AC.
- Thurs Sep 14
- Rice's Theorem
Material: Lecture 34 of AC.
- Homework 1 due. Homework 2 and Quiz 3 released
- Tues Sep 19
- Recursion Theorem
Material: Lecture 33, and 34 of ToC.
- Thurs Sep 21
- Isomorphism Theorems: Myhill and Rogers
Material: Lecture 34, Miscellaneous Exercises 107, 108, and 109 of ToC.
- Quiz 4 released
- Tues Sep 26
- Post's Theorem
Material: Lecture 37 of ToC.
- Thurs Sep 28
- Oracle Turing machines and Arithmetic Hierarchy
Material: Lecture 35, 36 of ToC, Supplementary Lecture J of AC.
- Homework 2 due. Homework 3 released
- Tues Oct 03
- Midterm 1: 7pm to 9pm.
- Thurs Oct 05
- Time and Space Complexity Classes
Material: Lecture 2 of ToC.
- Quiz 5 released
- Tues Oct 10
- Savitch's Theorem
Material: Lecture 2 of ToC.
- Thurs Oct 12
- Hierarchy Theorems
Material: Lecture 3 of ToC.
- Homework 3 due. Homework 4 and Quiz 6 released
- Tues Oct 17
- Nondeterministic Logspace
Material: Lecture 4 and 5 of ToC.
- Thurs Oct 19
- The Circuit Value Problem
Material: Lecture 6 of ToC.
- Tues Oct 24
- Structure within NP: Ladner Theorem
Material: Section 14.1 of Computational Complexity by Papadimitriou (copy posted on Moodle)
- Thurs Oct 26
- Structure within NP: Ladner Theorem (continued), Isomorphism conjecture, Berman/Mahaney Theorem.
Material: Section 14.1 and 14.2 of Computational Complexity by Papadimitriou (copy posted on Moodle)
- Homework 4 due. Homework 5 released
- Tues Oct 31
- Midterm 2 on November 1: 7pm to 9pm.
- Thurs Nov 02
- Alternation
Material: Lecture 7 of ToC
- Quiz 7 released
- Tues Nov 07
- PSPACE and Polynomial Time Hierarchy
Material: Lecture 8 and Lecture 9 of ToC
- Thurs Nov 09
- Polynomial Time Hierarchy
Material: Lecture 9 and 10 of ToC
- Homework 5 due. Homework 6 and Quiz 8 released
- Tues Nov 14
- Parallel Complexity
Material: Lecture 11 of ToC
- Thurs Nov 16
- Relation of NC to Time-Space Classes
Material: Lecture 12 of ToC
- Nov 20 to Nov 24
- Thanksgiving Break
- Tues Nov 28
- Probabilistic Complexity
Material: Lecture 13 of ToC
- Thurs Nov 30
- BPP and the Polynomial Time Hierarchy
Material: Lecture 14 of ToC
- Homework 6 due..
- Tues Dec 05
- Interactive Proofs
Material: Lecture 15 of ToC
- Thurs Dec 07
- Completing Lund-Fortnow-Karloff-Nisan Theorem: #SAT in IP; course wrapup and ICES forms
Material: Lecture 16 and 17 of ToC
- Quiz 9 released
- Tues Dec 12
- Shamir's Theorem: IP=PSPACE.
Material: Lecture 16 and 17 of ToC
- Mon Dec 18
- Final exam, 8:00am-11:00am