| Date |
Topics Covered |
Reading |
| 9/26 |
Course intro and info; Three problems; Automata |
0 |
| 9/29 |
Solving problems with Finite Automata; Example FAs; Alphabets/strings/languages |
1.1 |
| 10/1 |
DFA Defn; Delta hat; Proof of Simple property of delta hat (induction) |
Lecture notes |
| 10/3 |
Proving DFA minimality (pigeon-hole); Properties of Regular Languages |
Lect. notes, 1.1 |
| 10/6 |
Closures: union, complement, intersection (cross product construction); Nondeterminism |
1.2 |
| 10/8 |
Solving problems with NFAs; Defn of NFA |
1.2 |
| 10/10 |
NFA Computation; Closure properties of NFAs |
1.2 |
| 10/13 |
DFA-NFA equivalence (subset construction) |
1.3 |
| 10/15 |
Regular Expressions; NFA-DFA-regexp connection; Decision Procedures |
1.4, Lect. Notes |
| 10/17 |
Properties of Regular Languages: Pumping |
1.4 |
| 10/20 |
Pumping Lemma and Nonregular Languages |
1.4 |
| 10/22 |
PL examples; CFG definitions and examples; |
2.1 |
| 10/24 |
Computation with CFGs; CFG design; Parse Trees and Ambiguous Grammars |
2.1
|
| 10/27 |
MIDTERM Exam |
All the above |
| 10/29 |
Properties of CFLs: Closures; Chomsky Normal Form; Decision Procedures |
2.1, Lect. Notes |
| 10/31 |
Decision Procedures; Push Down Automata: Defns and Examples |
2.2 |
| 11/3 |
Computation with PDAs; Equivalence of PDAs and CFGs |
2.2 |
| 11/5 |
Closure of the Regular Languages intersection with CFLs; Pumping Lemma for CFLs |
2.3 |
| 11/7 |
Pumping Lemma Use; Finish CFLs |
2.3 |
| 11/10 |
Turing Machines: Motivation and Design; Definitions |
3.1 |
| 11/12 |
Definition of Computation; Turing Acceptable vs Turing Decidable Languages |
3.2 |
| 11/14 |
TM variants: multitape TMs; Non-deterministic TMs |
3.2 |
| 11/17 |
NTMs; Enumerators; Dove-tailing; Church-Turing Thesis |
3.2 |
| 11/19 |
Decidability; Languages vs Problems; Halting Problem |
Ch. 4 |
| 11/21 |
Undecidable Problems; Reductions; Atm, Etm |
Ch. 5 |
| 11/24 |
Mapping Reductions; Computable Functions; Language Hierarchy Revisited |
Ch. 5 |
| 11/26 |
Time Complexity of Algorithms |
Ch. 7, Lect. Notes |
| 11/28 |
Thankgsgiving, No Class |
Ch. 7 |
| 12/1 |
The classes P and NP; NP completeness |
Ch. 7, Lect. Notes |
| 12/3 |
Showing problems NP-complete |
Ch. 7, Lect. Notes |
| 12/5 |
NP-complete proofs; Review |
Ch. 7, Lect. Notes |
| 12/8 |
FINAL Exam |
10/29 and after |