Exams
Quiz 1, on Tue Sep 23
Quiz 2, on Tue Oct 21
Quiz 3, on Tue Nov 25
Final, on Dec 13 at 25
All exams are open book.

Homeworks
H1, due Thu Sep 18
H2, due Tue Oct 07
H3, due Thu Oct 16
H4, due Tue Nov 11
H5, due Thu Nov 20

Lecture Topics and Readings
Part 1: Automata and Languages
 Lecture 1 (Thu Sep 04): Introduction, models of computers, languages, finite automata.
  Book: 0, 1.1
  Homework 1 is handed out
 Lecture 2 (Tue Sep 09): DFAs, NFAs, regular expressions and the languages they recognize.
  Book: 1.2, 1.3
 Lecture 3 (Thu Sep 11): Nonregular languages, the pumping lemma for regular languages.
  Book: 1.4
 Lecture 4 (Tue Sep 16): Contextfree languages, pushdown automata.
  Book: 2.1, 2.2
 Lecture 5 (Thu Sep 18): Noncontextfree languages. Introduction to Turing machines.
  Book: 2.3
  Homework 1 is due
 Lecture 6 (Tue Sep 23): Quiz 1.
  Inclass quiz covering lectures 15, book chapters 1, 2.
Part 2: Computability Theory
 Lecture 7 (Thu Sep 25): The ChurchTuring Thesis. Basic Turing machines and variations.
  Book: 3.13.3
  Homework 2 is out
 Lecture 8 (Tue Sep 30): Decidable, recognizable, and enumerable languages.
  Book: 4.1, 4.2
 Lecture 9 (Thu Oct 02): Undecidability. The Halting Problem. NonTuring recognizability.
  Book: 4.2, 5.1
 Lecture 10 (Tue Oct 07): Computable functions. Mapping reducibility.
  Book: 5.3.
  Homework 2 is due; Homework 3 is out
 Lecture 11 (Thu Oct 09): No class today.
  No class today, enjoy the fall leaves
 Lecture 12 (Tue Oct 14): Undecidability of a simple game.
  Book: 5.2.
 Lecture 13 (Thu Oct 16): Selfreferencing machines. The Recursion Theorem. Computer viruses.
  Book: 6.1
  Homework 3 is due
 Lecture 14 (Tue Oct 21): Quiz 2.
  Inclass quiz focusing on lectures 713, book chapters 35, 6.1.
Part 3: Complexity Theory
 Lecture 15 (Thu Oct 23): Time complexity. Asymptotic function notation. Hierarchy Theorems. P. EXPTIME.
  Book: 7.1, 7.2, 9.1.
 Lecture 16 (Tue Oct 28): Nondeterministic polynomial time, NP. P vs NP.
  Book: 7.3
  Homework 4 is out
 Lecture 17 (Thu Oct 30): NPcompleteness. The CookLevin Theorem. Polynomialtime reducibility.
  Book: 7.4
 Lecture 18 (Tue Nov 04): Examples of NPcomplete languages.
  Book: 7.5.
 Lecture 19 (Thu Nov 06): Optimization vs decision problems. Higherorder and oracle complexity classes.
  Book: 9.2, 10.1.
 Lecture 20 (Tue Nov 11): Space complexity. Savitch's Theorem. PSPACEcompleteness.
  Book: 8.18.3
 Homework 4 is due; Homework 5 is out
 Lecture 21 (Thu Nov 13): The classes L and NL. Log space reducibility and NLcompleteness.
  Book: 8.4, 8.5
 Lecture 22 (Tue Nov 18): Probabilistic Turing machines. The classes BPP and RP.
  Book: 10.2.
 Lecture 23 (Thu Nov 20): Probabilistically checkable proofs.
  Homework 5 is due
 Lecture 24 (Tue Nov 25): Quiz 3.
  Inclass quiz focusing on lectures 1523, book chapters 710.2.
 Lecture 25 (Thu Nov 27): Thanksgiving Break.
  No class today, enjoy the holiday
 Lecture 26 (Tue Dec 02): Interactive Proof Systems. The classes IP and ZK. Cryptography.
  Book: 10.4, 10.6
 Lecture 27 (Thu Dec 04): No class today.
  This is the last day of classes.
  See Rebecca about extra office hours on Thursday, December 11 from 10:30am11:30am.
The cumulative final exam is on Saturday, Dec 13 from 25pm in Shaffer 202.
