| Date | Reading | Topic | Assignment |
|---|---|---|---|
| Aug 26 | Syllabus | Syllabus, policies, business | Read the Syllabus |
| Aug 28 | pp. 1-25 | Intro & basic concepts | hw1: 0.1-0.9 |
| Sep 02 | pp. 31-43 | Finite automata | hw2: 1.3, 1.6 |
| Sep 04 | pp. 47-54 | Nondeterminism | hw3: 1.7 (For parts e and f, if you are not yet familiar with regular expressions, the '*' superscript means "0 or more copies of" and the '+' superscript means "1 or more copies of") |
| Sep 09 | pp. 54-63 | Equivalence of DFAs and NFAs | hw4: 1.8-1.10, 1.16 |
| Sep 11 | pp. 63-69 | Regular expressions | hw5: 1.18, 1.20 |
| Sep 16 | pp. 69-76 | Kleene's theorem | hw6: 1.19, 1.21 |
| Sep 18 | pp. 77-83 | Nonregular languages | hw7: 1.29-1.30, 1.53 |
| Sep 23 | pp. 101-107 | Context free grammars | hw8: 2.3-2.4 |
| Sep 25 | pp. 107-111 | Ambiguity and normal form | hw9: 2.1, 2.8, 2.14, 2.27 |
| Sep 30 | pp. 111-116 | Pushdown automata | hw10: 2.5 (Just state diagrams will be sufficient -- you do not need to give informal descriptions.) |
| Oct 02 | pp. 117-124 | Equivalence of CFGs and PDAs | hw11: 2.11, 2.26 |
| Oct 07 | pp. 125-129 | Non-context free languages | hw12: 2.22, 2.30 |
| Oct 09 | Review | ||
| Oct 14 | Midterm | ||
| Oct 16 | pp. 165-173 | Turing machines | hw13: 3.1-3.2, 3.5, 3.7 |
| Oct 21 | pp. 174-182 | Variations on Turing machines | hw14: 3.8, 3.10-3.11 (See p. 185 for a definition of "implementation-level description".) |
| Oct 23 | pp. 182-187 | Algorithms | hw15: 3.15, 3.16a-d, 3.22 |
| Oct 28 | pp. 193-200 | Decidable languages | hw16: 4.1-4.4, 4.10 |
| Oct 30 | pp. 201-207 | Undecidability | hw17: 4.6-4.8, 4.12 |
| Nov 04 | pp. 207-210 | Undecidable and unrecognizable languages | hw18: 4.5, 4.24, 4.30 |
| Nov 06 | pp. 215-220 | Reducibility | hw19: 5.1 (consider reducing from ALLCFG, defined as undecidable in theorem 5.13), 5.24 |
| Nov 11 | pp. 220-226 | The Computation History Method (LBAs) | hw20: 5.30, plus invent an undecidable language and prove by reduction that it is undecidable (for 5.30, do not appeal to Rice's Theorem (as does the answer in the book), rather prove these by reduction) |
| Nov 13 | pp. 234-238 | Mapping [many-one] reducibility | hw21: 5.4, 5.9 |
| Nov 18 | pp. 275-284 | Big O analysis | hw22: 7.1-7.2, 7.28, except for 7.28, Don't prove NP-Completeness. Instead, produce an algorithm to solve the problem and analyze its complexity. |
| Nov 20 | pp. 284-291 | The class P | hw23: 7.3-7.4, 7.8-7.9 |
| Nov 25 | FALL RECESS | ||
| Nov 27 | FALL RECESS | ||
| Dec 02 | pp. 292-298 | The class NP | hw24: 7.5, 7.12 |
| Dec 04 | pp. 299-311 | The class NP-complete | hw25: 7.18, 7.21, 7.38, 7.41 (For r.21, Recall from your reading that UHAMPATH is NP-Complete) |
| Dec 09 | pp. 311-322 | More NP-complete problems | hw26: 7.29 |
| Dec 11 | Review | ||
| Dec 18 | Final Exam Window 10:00 a.m.-12:00 p.m. |
The schedule is subject to change.
The mapping is represented as 2e -> 3e, so, for example 0.11 in the second edition is 0.12 in the third 0.11 is a new problem the old 0.11 -> 0.12 4.5 is a new problem 4.5-4.7 -> 4.6-4.8 4.9 -> 4.10 4.11 -> 4.12 4.22 -> 4.24 4.28 -> 4.30 7.11 -> 7.12 7.17 -> 7.18 7.20 -> 7.21 7.26 -> 7.28 7.27 -> 7.29 7.36 -> 7.38 7.39 -> 7.41
