Outline of Course
| 6 Sep | Finite Automata | Section 1.1 | Homework 1 |
| 11 Sep | Nondeterminism | Section 1.2 | |
| 13 Sep | Regular Expressions | Section 1.3 | Homework 2 |
| 18 Sep | Nonregular Languages | Section 1.4 | |
| 20 Sep | Context-Free Grammars | Section 2.1 | Homework 3 |
| 25 Sep | Pushdown Automata | Section 2.2 | |
| 27 Sep | Non-Context-Free Languages | Section 2.3 | Homework 4 |
| 2 Oct | |||
| 4 Oct | Midterm 1 | ||
| 9 Oct | no class (Columbus Day observed) | ||
| 11 Oct | Turing Machines | Section 3.1 | Homework 5 |
| 16 Oct | Variants of Turing Machines | Section 3.2 | |
| 18 Oct | The Definition of Algorithm | Section 3.3 | Homework 6 |
| 23 Oct | Decidable Languages | Section 4.1 | |
| 25 Oct |
Undecidability |
Section 4.2 | Homework 7 |
| 30 Oct | Undecidable Problems from Language Theory | Section 5.1 | |
| 1 Nov | Homework 8 | ||
| 6 Nov | |||
| 8 Nov | Midterm 2 | ||
| 13 Nov |
Measuring Complexity The Class P |
Section 7.1 Section 7.2 |
Homework 9 |
| 15 Nov | The Class NP | Section 7.3 | |
| 20 Nov | NP-completeness | Section 7.4 | |
| 22 Nov | no class (Thanksgiving recess) | ||
| 27 Nov | Decidability of Logical Theories | Section 6.2 | Homework 10 |
| 29 Nov | Completeness Theorem | ||
| 4 Dec | Incompleteness Theorems | ||
| 6 Dec | Review | ||
| 8 - 15 Dec | Final Exams |
All topics shown above were covered, but dates are approximate.