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