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
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.