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