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 16: More Reductions (10/28) Sipser 5.1
- Lecture 17: Linear Bounded Automata and Mapping Reducibility. Sipser 5.1, 5.3(10/30)
- Lecture 18: Information, Randomness, and Compression: Kolmogorov Complexity. Sipser 6.4 (11/4)
- Lecture 19: Kolmogorov complexity is not computable, and Godel's incompleteness theorem via Kolmogorov Complexity. (Not in Sipser) (11/6)
- Lecture 20: Begin time complexity: Definitions of P and NP, robustness of the model. Sipser 7.1 (11/11)
- Lecture 21: Equivalence of 2 definitions of NP. How to show problems are in NP. Sipser 7.3 (11/13)
- Lecture 22: Formal definition of NP completeness and polynomial time reducibility. Sipser 7.4 (11/18)
- Lecture 23: Reductions -- NP Completeness of CLIQUE, INDEPENDENT-SET, VERTEX-COVER, and HAMILTONINAN-PATH. Sipser 7.5 (11/20)
- Lecture 24: Cook's Theorem. Sipser 7.4 (11/25)
- Lecture 25: Approximation Algorithms. Sipser 10.1 and extra material. (12/2)
- Lecture 26: Randomized algorithms, 2SAT, and random walks. Not in Sipser. (12/4)
- Lecture 27: Last class -- The amazing weighted majority algorithm. Not in Sipser. (12/9)
- Final Exam: Monday 12/15 12:00-2:00 in DRLB A1, A8

- 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.
- Problem Set 5. Due 11/18/14.
- Problem Set 6. Due 12/4/14.