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 C1 to C28, 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.
| Class | Date | Lecture Topics | Book Readings |
|---|---|---|---|
| C1 | 8/26 | Administrative; Logic and Proofs | 0 |
| C2 | 8/28 | ||
| C3 | 9/2 | Mathematical Objects | |
| C4 | 9/4 | ||
| C5 | 9/9 | Proofs by Induction | |
| C6 | 9/11 | Finite Automata | 1.1-1.2 |
| C7 | 9/16 | ||
| C8 | 9/18 | ||
| C9 | 9/23 | Regular Expressions | 1.3 |
| C10 | 9/25 | ||
| C11 | 9/30 | Non-Regular Languages | 1.4 |
| C12 | 10/2 | ||
| C13 | 10/7 | ||
| C14 | 10/9 | Midterm Exam #1 | |
| 10/14 | Fall Break (no class) | ||
| C15 | 10/16 | Context-Free Grammars | 2.1 |
| C16 | 10/21 | Pushdown Automata | 2.2 |
| C17 | 10/23 | Non-Context-Free Languages | 2.3 |
| C18 | 10/28 | Pumping Lemma for CFLs | 2.3 |
| C19 | 10/30 | Deterministic CFL Recognition | 2.4 |
| C20 | 11/4 | Turing Machines | 3.1 |
| C21 | 11/6 | ||
| C22 | 11/11 | Decidability | 4.1 |
| C23 | 11/13 | Midterm Exam #2 | |
| C24 | 11/18 | Undecidability | 4.2 |
| C25 | 11/20 | Reducibility | 5.1,5.3 |
| C26 | 11/25 | ||
| 11/27 | Thanksgiving (no class) | ||
| C27 | 12/2 | Post Correspondence Problem | 5.2 |
| C28 | 12/4 | Recursion Theorem | 6.1 |
| F | 12/11 | Final Exam |