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