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
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