Schedule
Readings are in Sipser's Introduction to the Theory of Computation, 2nd ed. unless otherwise specified.
| # | Day | Date | Topic & Lecture Notes | Readings | Other Handouts | Problem Sets CS121 | Problem Sets CSCI E-121 |
|---|---|---|---|---|---|---|---|
1 | Tu | Sept. 2 | Introduction and Overview | Preface | |||
Unit 1: Finite Automata | |||||||
2 | Th | Sept. 4 | Strings, Languages, and Induction | Ch. 0 | |||
3 | Tu | Sept. 9 | Finite Automata | Sec. 1.1-1.2 | PS 0 due | ||
4 | Th | Sept. 11 | NFAs vs. DFAs, Closure Properties | Sec 1.1-1.2 | PS 0 due (Fri) | ||
5 | Tu | Sept. 16 | Regular Expressions | Sec 1.3 | PS 1 due | ||
6 | Th | Sept. 18 | Countability and Uncountaibility | Sec 1.3, Sec 4.2 (pp. 174-178) | PS 1 due (Fri) | ||
7 | Tu | Sept. 23 | The Pumping Lemma and Nonregular languages | Sec 4.2 (pp. 174-178), Sec. 1.4 | PS 2 due | ||
8 | Th | Sept. 25 | DFA Minimization Context Free Grammars | Sec. 1.4 | PS 2 due (Fri) | ||
Unit 2: Context-Free Languages | |||||||
9 | Tu | Sept. 30 | Ambiguity of Context-free Grammars Pushdown Automata | Sec. 2.1 | PS 3 due | ||
10 | Th | Oct. 2 | Problem solving session | Sec. 2.2 | PS 3 due (Fri) | ||
11 | Tu | Oct. 7 | CFGs vs. PDAs, Non-CF Languages | Sec. 2.2, 2.3 | PS 4 due | ||
12 | Th | Oct. 9 | CF Recognition | Sec. 2.1 | PS 4 due (Fri) | ||
Unit 3: Computability | |||||||
13 | Tu | Oct. 14 | CFL wrap-up Hilbert and Turing | Sec. 3.1 | |||
Th | Oct. 16 | Midterm Examination on Material thru Oct. 10
| |||||
14 | Tu | Oct. 21 | Turing Machines and the Church-Turing Thesis | Sec. 3.2, 3.3 | PS 5 due | ||
15 | Th | Oct. 23 | Recognizability & Decidability | Sec. 3.2, 3.3, 4.1 | PS 5 due (Fri) | ||
16 | Tu | Oct. 28 | Turing's Theorem | Sec. 4.1, 4.2 | PS 6 due | ||
17 | Th | Oct. 30 | Reducibility | Sec. 4.2, 5.1 | PS 6 due (Fri) | ||
18 | Tu | Nov. 4 | Partial Recursive Functions, Undecidable questions | Sec. 5.1, 5.3 |
PS 7 due
| ||
Unit 4: Computational Complexity | |||||||
19 | Th | Nov. 6 | Computational Complexity | Sec. 7.1 | PS 7 due (Fri) | ||
20 | Tu | Nov. 11 | Polynomial Time | Sec. 7.2 | PS 8 due | ||
21 | Th | Nov. 13 | NP | Sec. 7.3 | PS 8 due (Fri) | ||
22 | Tu | Nov. 18 | P vs. NP, NP-completeness | Sec. 7.4, 7.5 | |||
23 | Th | Nov. 20 | More NP-completeness | Sec. 7.5 | |||
24 | Tu | Nov. 25 | Cook-Levin and More on NP | Sec. 7.4, 10.4 | |||
Th | Nov. 27 | NO CLASS - THANKSGIVING | |||||
25 | Tu | Dec. 2 | Glimpses Beyond & Conclusions | Sec. 10.4 | PS 9 due (Tuesday, no late date) | PS9 due (Tuesday) | |
TBD | Review Section | ||||||
TBD | Final Examination 2013 Final Exam and Solutions | ||||||