Theory of Computation

CSCI 341, Fall 2016

Course Info

Recitation

  1. 2016-08-26. Recitation 1
  2. 2016-08-30. Recitation 2
  3. 2016-09-06. Recitation 3
  4. 2016-09-13. (prog. assign. 1)
  5. 2016-09-20. Recitation 4
  6. 2016-09-27. (prog. assign. 2)
  7. 2016-10-04. Recitation 5
  8. 2016-10-18. Recitation 6
  9. 2016-10-25. (prog. assign. 3)
  10. 2016-11-01. Recitation 7
  11. 2016-11-08. Recitation 8 Solution Here.
  12. 2016-11-15. (prog. assign. 4)
  13. 2016-11-29. Recitation 9

Readings

From the book "Introduction to the Theory of Computation" by Michael Sipser.
  1. 2016-08-22 Ch 0.1 2016-08-23 Ch 0.2 2016-08-24 Ch 0.2
  2. 2016-08-29 Ch 0.2 2016-08-31 Ch 0.3 2016-09-02 Ch 0.4
  3. 2016-09-05 Ch 0.4, Ch 4.2 2016-09-07 Ch 0.2 (Strings) 2016-09-09 Ch 1.3 (Regexp)
  4. 2016-09-12 Ch 1.3 2016-09-14 Ch 1.2 (NFA) 2016-09-16 Ch 1.2 (NFA)
  5. 2016-09-19 Ch 1.1 (DFA) 2016-09-21 Ch 1.1 2016-09-23 Ch 1.3
  6. 2016-09-26 Inter, Compl 2016-09-28 Minimization 2016-09-30 Exam1
  7. 2016-10-03 Minimization 2016-10-05 Ch 1.4 2016-10-07 Ch 1.4
  8. 2016-10-10 Fall break 2016-10-13 Ch 3.1 2016-10-15 Ch 3.1
  9. 2016-10-17 Ch 3.2 2016-10-20 Ch 3.2 (multitape) 2016-10-15 Ch 3.2 (NTM)
  10. 2016-10-24 Ch 3.2 (NTM) 2016-10-26 Universal TM 2016-10-27 Ch 3.3, 4.1
  11. 2016-10-31 Ch 4.2 (undecidability) 2016-11-02 Ch 5.1 2016-11-04 Ch 5.2
  12. 2016-11-07 Ch 5.2 (PCP) 2016-11-09 Ch 5.3 2016-11-11 Exam2
  13. 2016-11-14 Ch 7.1-7.2 (P) 2016-11-16 Ch 7.3 2016-11-18 Ch 7.3
  14. 2016-11-21/23/25 Thanksgiving Break
  15. 2016-11-28 Ch 7.3 2016-11-30 Ch 8.1-8.2 (PSPACE, Savitch's Theorem)
    2016-12-02 Ch 9.1 (Hierarchy Theorems)

Homework

Programming Assignments

Extra material