TAs: Nimit Singhania (Head TA), Lingbin Cai, Jonathan Chen, Meryem Essaidi, Jake Hart, Rohit Kothur

Recitation: Monday 4:30-5:30 DRLB A1

Prerequisites: CIS 160 and mathematical maturity.

Course Software: We will be using Piazza for questions. Ask and answer questions here (this counts towards your participation grade). You can turn in assignments and see grades using Canvas.

Textbook: Introduction to the Theory of Computation (3rd Edition), by Michael Sipser.

- Lecture 1: Overview. Introduction to finite automata. Sipser 1.1. (8/28)
- Lecture 2: More examples of finite automata, and formal definitions of acceptance, languages, and regular languages. Sipser 1.1 (9/2)
- Lecture 3: Definition of regular operations + proof of closure under union. Introduction to non-determinism. Sipser 1.1, 1.2. (9/4)
- Lecture 4: Formal definition of NFAs and Equivalence between NFAs + DFAs. Sipser 1.2 (9/9)
- Lecture 5: Closure under the regular operations. Sipser 1.2 (9/11)
- Lecture 6: Regular Expressions and equivalence with regular languages. Sipser 1.3 (9/16)
- Lecture 7: Finish equivalence of regular expressions and regular languages. Sipser 1.3 (9/18)
- Lecture -- Non-regular languages and the pumping lemma (9/23)
- Lecture -- Begin Turing machines (9/25)
- Lecture -- Continue Turing machines (9/30)
- Lecture -- More Turing machines... (10/2)
- Lecture -- Equivalence of Turing machines and enumerators, and the decidability of DFA equivalence (10/7)
- Midterm -- In Fagin Hall(10/14)
- Lecture -- Uncountability of the reals, and existence of undecidable problems (10/16)
- Lecture -- The halting problem, and reductions. (10/21)
- Lecture -- More undecidable problems. Reductions in Computability (10/23)
- Lecture -- More Reductions (10/28)
- Lecture -- Information, Randomness, and Compression: Kolmogorov Complexity (10/30)
- Lecture -- Godel's incompleteness theorem (11/4)
- Lecture -- Begin time complexity: P and NP (11/6)
- Lecture -- NP hardness and completeness, and polynomial time reductions (11/11)
- Lecture -- Cook's Theorem: SAT is NP Complete (11/13)
- Lecture -- NP Completeness of CLIQUE, INDEPENDENT-SET, VERTEX-COVER, and HAMILTONINAN-PATH (11/17)
- Lecture -- Approximation Algorithms (11/21)
- Lecture -- Advanced Topics (Randomness) (11/24)
- Lecture -- Advanced Topics (PSPACE) (11/28)
- Lecture -- Advanced Topics Public Key Cryptography (12/4)
- Last Class -- The power of algorithms! (12/9)
- Final Exam -- (TENTATIVE DATE) (12/15 12:00-2:00)

- Problem Set 1. Due 9/9/14.
- Problem Set 2. Due 9/23/14.
- Problem Set 3. Due 10/7/14.