Exams
Quiz 1, on Mon Oct 01
Quiz 2, on Mon Oct 29
Quiz 3, on Mon Dec 03
Final, on Sat Dec 15, 9am12pm
All exams are open book.
Held in Maryland 310.

Homeworks
H1, due Wed Sep 19
H2, due Wed Sep 26
H3, due Wed Oct 17
H4, due Wed Oct 24
H5, due Mon Nov 19
H6, due Wed Nov 28

Lecture Topics and Readings
Part 1: Automata and Languages
 Lecture 1 (Mon Sep 10): Introduction, models of computers, languages, finite automata.
  Book: 0, 1.1
  Homework 1 is handed out
 Lecture 2 (Wed Sep 12): DFAs and the languages they recognize.
  Book: 1.1, 1.2
 Lecture 3 (Mon Sep 17): NFAs, regular expressions and the languages they recognize.
  Book: 1.2, 1.3
 Lecture 4 (Wed Sep 19): Nonregular languages, the pumping lemma for regular languages.
  Book: 1.4
  Homework 1 is due; Homework 2 is out
 Lecture 5 (Mon Sep 24): Contextfree languages, pushdown automata.
  Book: 2.1, 2.2
 Lecture 6 (Wed Sep 26): Noncontextfree languages. Introduction to Turing machines.
  Book: 2.3
  Homework 2 is due
 Lecture 7 (Mon Oct 1): Quiz 1.
  Inclass quiz covering lectures 16, book chapters 1, 2.
Part 2: Computability Theory
 Lecture 8 (Wed Oct 3): The ChurchTuring Thesis. Basic Turing machines and variations.
  Book: 3.13.3
 Lecture 9 (Mon Oct 8): Decidable, recognizable, and enumerable languages.
  Book: 4.1, 4.2
  Homework 3 is out
 Lecture 10 (Wed Oct 10): Undecidability. The Halting Problem. NonTuring recognizability.
  Book: 4.2, 5.1
 Lecture 11 (Mon Oct 15): Fall Break Day
  No class today, enjoy the fall leaves
 Lecture 12 (Wed Oct 17): Undecidability. Computation histories.
  Book: 5.2.
  Homework 3 is due; Homework 4 is out
 Lecture 13 (Mon Oct 22): Computable functions. Mapping reducibility. Turing reducibility.
  Book: 5.3, 6.3.
 Lecture 14 (Wed Oct 24): Selfreferencing machines. The Recursion Theorem. Computer viruses.
  Book: 6.1
  Homework 4 is due
 Lecture 15 (Mon Oct 29): Quiz 2.
  Inclass quiz focusing on lectures 814, book chapters 35, 6.1, 6.3.
Part 3: Complexity Theory
 Lecture 16 (Wed Oct 31): Time complexity. Asymptotic function notation. Hierarchy Theorems. P. EXPTIME.
  Lecturer: Omar Zaidan
  Book: 7.1, 7.2, 9.1.
  Happy Halloween!
 Lecture 17 (Mon Nov 5): Nondeterministic polynomial time, NP. P vs NP.
  Book: 7.3
  Homework 5 is out
 Lecture 18 (Wed Nov 7): NPcompleteness. The CookLevin Theorem. Polynomialtime reducibility.
  Book: 7.4
 Lecture 19 (Mon Nov 12): Examples of NPcomplete languages.
  Book: 7.5.
 Lecture 20 (Wed Nov 14): Optimization vs decision problems. Higherorder and oracle complexity classes.
  Book: 9.2, 10.1.
 Lecture 21 (Mon Nov 19): Space complexity. Savitch's Theorem. PSPACEcompleteness.
  Book: 8.18.3
 Homework 5 is due; Homework 6 is out
 Lecture 22 (Wed Nov 21): The classes L and NL. Log space reducibility and NLcompleteness.
  Book: 8.4, 8.5
Thanksgiving break
 Lecture 23 (Mon Nov 26): Probabilistic Turing machines. The classes BPP and RP.
  Book: 10.2.
 Lecture 24 (Wed Nov 28): Probabilistically checkable proofs.
  Homework 6 is due
 Lecture 25 (Mon Dec 3): Quiz 3.
  Inclass quiz focusing on lectures 1624, book chapters 710.2.
 Lecture 26 (Wed Dec 5): Interactive Proof Systems. The classes IP and AM. Cryptography.
  Lecturer: Seny Kamara
  Book: 10.4, 10.6
  See Seny's excellent slides!
 Lecture 27 (Mon Dec 10): Review. Survey of advanced topics.
  This is the last day of classes.
The cumulative final exam is Saturday, December 15 from 9am12pm in Maryland 310.
