| Week | Dates | Material covered | Section |
|---|---|---|---|
| 1 | Jan 1–5 | Discussion of syllabus Proof techniques |
Sections 1.1–1.4, pages 3–28 Sections 2.1–2.5, pages 43–72 |
| 2 | Jan 8–12 | Languages Regular Languages and Finite Automata (FA) |
Section 1.5, pages 28–32 Sections 3.1–3.3, pages 85–105 |
| 3 | Jan 15–19 | Distinguishing one string from another Nondeterministic FA, HW #1 |
Sections 3.4–3.5, pages 105–112 Section 4.1, pages 123–133 |
| 4 | Jan 22–26 | Nondeterministic FA with Lambda-transitions Kleene's Theorem |
Sections 4.2–4.3, pages 133–154 |
| 5 | Jan 29–Feb 2 | Minimal FA Pumping Lemma for regular languages, HW #2 |
Sections 5.1–5.2, pages 168–179 Sections 5.3–5.5, pages 180–191 |
| 6 | Feb 5–9 | Context-free grammars Regular grammars |
Sections 6.1–6.2, pages 203–217 Section 6.3, pages 217–220 |
| 7 | Feb 12–16 | Derivation trees and ambiguity Pushdown Automata, DPDA, Midterm Exam |
Sections 6.4–6.5, pages 220–237 Sections 7.1–7.3, pages 251–263 |
| 8 | Feb 19–23 | pal is not DCFL PDA = CFG |
Section 7.3, pages 264–265 Sections 7.4–7.5, pages 265–280 |
| 9 | Feb 26–Mar 2 | Winter Break | - |
| 10 | Mar 5–9 | Pumping lemma for CFL's | Section 8.1, pages 297–304 |
| 11 | Mar 12–16 | Instersections, complements, and decision problems of CFL's Turing Machines, HW #3 |
Sections 8.2–8.3, pages 306–312 Section 9.1, pages 319–327 |
| 12 | Mar 19–23 | Combining TM's, Multitape TM's Nondeterministic TM's, Universal TM's |
Sections 9.3–9.4, pages 332–341 Sections 9.5–9.6, pages 341–352 |
| 13 | Mar 26–30 | Recursive and recursively enumerable languages Unrestricted grammars A nonrecursive language, HW #4 |
Sections 10.1–10.3, pages 365–380 Section 10.5, pages 387–397 Section 11.1, pages 407–410 |
| 14 | Apr 2–6 | Unsolvable problems Growth rates of functions Time and Space complexity of TM's |
Sections 11.1–11.4, pages 410–422 Sections 13.1–13.2, pages 481–492 |
| 15 | Apr 9–13 | P and NP Polynomial-time reductions and NP-completeness Cook's Theorem, Review |
Sections 14.1–14.3, pages 500–517 |
| 16 | Apr 16–20 | NP-complete Problems | Section 14.4, pages 517–522 |