The following course schedule is TENTATIVE and subject to change. Readings are taken from Introduction to the Theory of Computation, 3rd edition by Michael Sipser.
There are a total of 28 class meetings, which are numbered below from 1-A to 14-B, followed by a final examination. You can map these to dates by consulting the University calendar for the current semester. The two Midterm Exams will occur during regular class periods, as indicated. The Final Exam will occur at the officially scheduled date and time during the Final Exam period.
| Week-Class | Lecture Topics | Book Readings |
|---|---|---|
| 1-A | Administrative; Logic and Proofs | 0 |
| 1-B | Mathematical Objects | |
| 2-A | ||
| 2-B | Proofs by Induction | |
| 3-A | Finite Automata | 1.1-1.2 |
| 3-B | ||
| 4-A | ||
| 4-B | ||
| 5-A | Regular Expressions | 1.3 |
| 5-B | ||
| 6-A | ||
| 6-B | ||
| 7-A | Non-Regular Languages | 1.4 |
| 7-B | Midterm Exam #1 | |
| Spring Break (no class) | ||
| Spring Break (no class) | ||
| 8-A | Context-Free Grammars | 2.1 |
| 8-B | Pushdown Automata | 2.2 |
| 9-A | Pumping Lemma for CFLs | 2.3 |
| 9-B | Deterministic CFL Recognition | 2.4 |
| 10-A | Turing Machines | 3.1 |
| 10-B | ||
| 11-A | Decidability | 4.1 |
| 11-B | ||
| 12-A | Undecidability | 4.2 |
| 12-B | Midterm Exam #2 | |
| 13-A | ||
| 13-B | Reducibility | 5.1-5.3 |
| 14-A | ||
| 14-B | Recursion Theorem | 6.1 |
| F | Final Exam |