Theory of Computation
CSCI 341, Fall 2016
Course Info
Recitation
Readings
From the book
"Introduction to the Theory of Computation" by Michael Sipser.
- 2016-08-22 Ch 0.1 2016-08-23 Ch 0.2 2016-08-24 Ch 0.2
- 2016-08-29 Ch 0.2 2016-08-31 Ch 0.3 2016-09-02 Ch 0.4
- 2016-09-05 Ch 0.4, Ch 4.2 2016-09-07 Ch 0.2 (Strings) 2016-09-09 Ch 1.3 (Regexp)
- 2016-09-12 Ch 1.3 2016-09-14 Ch 1.2 (NFA) 2016-09-16 Ch 1.2 (NFA)
- 2016-09-19 Ch 1.1 (DFA) 2016-09-21 Ch 1.1 2016-09-23 Ch 1.3
- 2016-09-26 Inter, Compl 2016-09-28 Minimization 2016-09-30 Exam1
- 2016-10-03 Minimization 2016-10-05 Ch 1.4 2016-10-07 Ch 1.4
- 2016-10-10 Fall break 2016-10-13 Ch 3.1 2016-10-15 Ch 3.1
- 2016-10-17 Ch 3.2 2016-10-20 Ch 3.2 (multitape) 2016-10-15 Ch 3.2 (NTM)
- 2016-10-24 Ch 3.2 (NTM) 2016-10-26 Universal TM 2016-10-27 Ch 3.3, 4.1
- 2016-10-31 Ch 4.2 (undecidability) 2016-11-02 Ch 5.1 2016-11-04 Ch 5.2
- 2016-11-07 Ch 5.2 (PCP) 2016-11-09 Ch 5.3 2016-11-11 Exam2
- 2016-11-14 Ch 7.1-7.2 (P) 2016-11-16 Ch 7.3 2016-11-18 Ch 7.3
- 2016-11-21/23/25 Thanksgiving Break
- 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