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 8: Non-regular languages and the pumping lemma. Sipser 1.4 (9/23)
- Lecture 9: More pumping lemma examples, begin Turing machines. Sipser 1.4, 3.1(9/25)
- Lecture 10: Formal definition of Turing Machines. Sipser 3.1 (9/30)
- Lecture 11: More Turing machine constructions... Sipser 3.1 (10/2)
- Lecture 12: Equivalence of Turing Machines and Multi-Tape Turing machines. Decidability of several easy languages. Sipser 3.2, 3.3 (10/7)
- Midterm -- In Fagin Hall(10/14)
- Lecture 13: Uncountability of the reals, and existence of non Turing Recognizable problems Sipser 4.2 (10/16).
- Lecture 14: Undecidability of A_TM and the Halting problem. Definition of co-Turing-Recognizability. Sipser 4.2, 5.1 (10/21)
- Lecture 15: Undecidability of E_TM and Regular_TM, statement of Rice's theorem. Sipser 5.1 (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.
- Problem Set 4. Due 11/4/14.