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.