1 |
Introduction, Finite Automata, Regular Expressions |
|
2 |
Nondeterminism, Closure Properties, Regular Expressions ↔ FA |
|
3 |
Regular Pumping Lemma, Context Free Languages |
|
4 |
Pushdown Automata, CFG ↔ PDA |
|
5 |
CF Pumping Lemma, Turing Machines |
Homework 1 due |
6 |
TM Variants, Church-Turing Thesis |
|
7 |
Decision Problems for Automata and Grammars |
|
8 |
Undecidability |
|
9 |
Reducibility |
Homework 2 due |
10 |
Linearly Bounded Automata, PCP |
|
11 |
Recursion Theorem and Logic |
|
12 |
Time Complexity |
Homework 3 due |
13 |
Midterm Exam |
|
14 |
P and NP, SAT, Poly-time Reducibility |
|
15 |
NP-Completeness |
|
16 |
Cook-Levin Theorem |
Homework 4 due |
17 |
Space Complexity |
|
18 |
PSPACE, TQBF, Savitch's Theorem |
|
19 |
Games, Generalized Geography |
|
20 |
L and NL, NL= coNL |
Homework 5 due |
21 |
Hierarchy Theorems |
|
22 |
Provably Intractable Problems, Oracles |
|
23 |
Probabilistic Computation, BPP |
|
24 |
Probabilistic Computation (cont.) |
|
25 |
Interactive Proof Systems, IP |
Homework 6 due |
26 |
Topic |
|
27 |
Final Exam |
|