Exams
Quiz 1, on Wed Sep 23
Quiz 2, on Mon Oct 26
Quiz 3, on Wed Dec 02
Final, on Thu Dec 17
All exams are open book.

Homeworks
H1 LaTeX, out 09/09, due 09/21
H2 LaTeX, out 09/30, due 10/07
H3 LaTeX, out 10/07, due 10/19
H4 LaTeX, out 11/02, due 11/16
H5 LaTeX, out 11/16, due 11/23

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