| Date | Topic and reading |
|---|---|
| Thu, Sep. 24 | Intro; mathematical preliminaries Reading: Sipser 0 Homework #1 out |
| Tue, Sep. 29 | Deterministic finite automata Reading: Sipser 1.1 |
| Thu, Oct. 1 | Nondeterministic finite automata Reading: Sipser 1.2 Homework #1 due, #2 out |
| Tue, Oct. 6 | Regular languages and regular expressions Reading: Sipser 1.3 |
| Thu, Oct. 8 | Nonregular languages and the pumping lemma Reading: Sipser 1.4 Homework #2 due |
| Tue, Oct. 13 | Context-free grammars Reading: Sipser 2.1 Homework #3 out |
| Thu, Oct. 15 | Midterm #1 |
| Tue, Oct. 20 | Pushdown automata Reading: Sipser 2.2 |
| Thu, Oct. 22 | Non-context-free languages Reading: Sipser 2.3 |
| Tue, Oct. 27 | Advanced topics in context-free languages Reading: Sipser 2, exercises and problems Homework #3 due, #4 out |
| Thu, Oct. 29 | Context-free languages: catchup Reading: |
| Tue, Nov. 3 | Turing machines Reading: Sipser 3.1 Homework #4 due |
| Thu, Nov. 5 | Turing machine variants and the Church-Turing thesis Reading: Sipser 3.2 and 3.3 Homework #5 out |
| Tue, Nov. 10 | Midterm #2 |
| Thu, Nov. 12 | Decidable languages Reading: Sipser 4.1 |
| Tue, Nov. 17 | Undecidable languages Reading: Sipser 4.2 Homework #5 due, #6 out |
| Thu, Nov. 19 | Reducibility Reading: Sipser 5.1 and 5.3 |
| Tue, Nov. 24 | The recursion theorem Reading: Sipser 6.1 Homework #6 due, #7 out |
| Thu, Nov. 26 | Thanksgiving—No Class |
| Tue, Dec. 1 | Introduction to Complexity Reading: Sipser 7.x |
| Thu, Dec. 3 | Catchup and advanced topics
Reading: Homework #7 due |
| Fri, Dec. 11 | Final Exam |