CS4510: Automata and Complexity
Fall 2019, MW 3-4:15pm in Clough 144
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
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.
- Aug 19. Models of Computation. DFAs and TMs. L 8/19,draft 8/19
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
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
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
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
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
Tex for HW6,
due: Oct. 18th, 12pm
- Oct 16. Pushdown automata.
- Oct 21. Review.
- Oct 23. Exam II.
- Oct 28. TMs: Space Complexity. L10/28,
- Oct 30. Space and Time hierarchies. L10/30
Tex for HW7,
due: Nov. 6th, 3pm
- Nov 4. P, NP.
L11/4, draft 11/4
- Nov 6. Reduction.
Tex for HW8,
due: Nov. 18th, 3pm
- Nov 11, 13. NP-completeness.
- 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.