Outline of Course
| 11 Sep | Finite Automata | Section 1.1 | Homework 1 |
| 15 Sep | Nondeterminism | Section 1.2 | |
| 18 Sep | Regular Expressions | Section 1.3 | Homework 2 |
| 22 Sep | Minimization | ||
| 25 Sep | Nonregular Languages | Section 1.4 | |
| 29 Sep | Context-Free Grammars | Section 2.1 | |
| 2 Oct | Pushdown Automata | Section 2.2 | Homework 3 |
| 6 Oct | Non-Context-Free Languages | Section 2.3 | |
| 9 Oct | CFG Hierarchy | Homework 4 | |
| 13 Oct | Introduction to Decidability | ||
| 16 Oct | Midterm | ||
| 20 Oct | Turing Machines | Section 3.1 | |
| 23 Oct | Variants of Turing Machines | Section 3.2 | Homework 5 |
| 27 Oct | The Definition of Algorithm | Section 3.3 | |
| 30 Oct | Decidable Languages | Section 4.1 | Homework 6 |
| 3 Nov |
Undecidability |
Section 4.2 | |
| 6 Nov | Undecidable Problems from Language Theory | Section 5.1 | |
| 10 Nov | Midterm | ||
| 13 Nov |
Measuring Complexity The Class P |
Section 7.1 Section 7.2 |
Homework 7 |
| 17 Nov | The Class NP | Section 7.3 | |
| 20 Nov | NP-completeness | Section 7.4 | Homework 8 |
| 24 Nov | Decidability of Logical Theories | Section 6.2 | |
| 27 Nov | no class | ||
| 1 Dec | Completeness and Incompleteness Theorems | ||
| 4 Dec | Probabilistic Algorithms | Section 10.2 | |
| 8 Dec | Quantum Algorithms | ||
| 11 - 18 Dec | Final Exam |
Topics shown in bold will definitely be covered. Other topics will be covered only if time permits.