This is a course about models of computation and reasoning about their power.

(Textbook: "Introduction to the Theory of Computation," Michael Sipser)

**Instructor**: Santosh Vempala. Office Hours: W:11-12:30 and by appt. Office Location: Klaus 2224A

**TAs**:

Aditi Laddha. OH: MW 1-2:30pm

Yanan Wang. OH: TR: 3:30-5pm

Abrahim Ladha. OH: F: 1-4pm

Nathania Nah. OH: F: 10am-1pm

Xiaofu Niu. OH: MW: 11:30am-1pm

Richard (Zijie) Meng. OH: MW: 10-11:30am

Nicolas Soong. OH: R: 12-3pm

Frederic Faulkner. OH: TR:10-11:30am

TA office hours will be between room 2116 and room 2124 on the second floor of Klaus (**AS DEFAULT**), either in/near 2108.

Sometimes the TAs will reserve rooms in Clough.

**Schedule** (tentative):

- Aug 19. Models of Computation. DFAs and TMs. L 8/19,draft 8/19

HW1, Tex for HW1, due: Aug. 26th, 3pm - Aug 21. Languages and Machines. L 8/21,draft 8/21
- Aug 26. Turing Machine and DFA. L 8/26,draft 8/26

HW2, Tex for HW2, due: Sept. 4th, 3pm - Aug 28. Nondeterminism, Regular Languages. L 8/28,draft 8/28
- Sep 4. Undecidability. L 9/4,draft 9/4
- Sep 9. Pumping. L 9/9,draft 9/9

HW3, Tex for HW3, due: Sept. 16th, 3pm

- Sep 11. Myhill-Nerode. L 9/11,draft 9/11
- Sep 16. Review.
- Sept 18. Exam I.
- Sep 23. Probabilistic Finite automata. L 9/23,draft 9/23
- Sep 25. Markov chains.
L 9/25,draft 9/25

HW4, Tex for HW4, due: Oct. 2nd, 3pm - Sep 30. Learning a DFA. L 9/30,draft 9/30
- Oct 2. Learning a DFA.
L 10/2,draft 10/2

HW5, Tex for HW5, due: Oct. 9th, 3pm - Oct 7. Context Free Grammars, Pushdown Automata, Chomsky Normal Form. L 10/7,draft 10/7
- Oct 9. Pumping Context Free Grammars.
L 10/9,draft 10/9

HW6, Tex for HW6, due: Oct. 18th, 12pm - Oct 16. Pushdown automata.
L10/16,draft 10/16

- Oct 21. Review.
- Oct 23. Exam II.
- Oct 28. TMs: Space Complexity. L10/28,
draft 10/28

- Oct 30. Space and Time hierarchies. L10/30
draft 10/30

HW7, Tex for HW7, due: Nov. 6th, 3pm - Nov 4. P, NP. L11/4, draft 11/4
- Nov 6. Reduction.
L11/6,draft 11/6

HW8, Tex for HW8, due: Nov. 18th, 3pm - Nov 11, 13. NP-completeness. L11/11, L11/13
- Nov 18. Review
- Nov 20. Exam III.
- Nov 25. Computing and the brain.
- Dec 2. Course Review.
- Dec 6. Final Exam.

**Grading**: HW: 20%, 3 midterm exams: 20% each, Final: 20%.

We'll take the best n-1 HWs for your grade. No late HWs.