TENTATIVE SCHEDULE FOR CPT S 317 (Spring 2010)
* Homework links will be activated on their posting dates.
| Class | Day | Date | Topic | Readings (sections) |
Assignments* |
|
| Due | Posting | |||||
| 1 | M | 1/11 | Course introduction, introduction to automata theory | Chapter 1 | ||
| 2 | W | Formal proofs | ||||
| 3 | F | Introduction to Gradiance - demo | ||||
| --- | M | 1/18 | MLK Day (holiday) | |||
| 4 | W | Finite Automata (DFA & NFA) | Chapter 2 | HW1 | ||
| 5 | F | Equivalence of DFA & NFA, epsilon-transitions | ||||
| 6 | M | 1/25 | Regular expressions | Chapter 3 | ||
| 7 | W | HW1 | HW2 | |||
| 8 | F | Regular language properties: pumping lemma | Chapter 4 | |||
| 9 | M | 2/1 | Closure properties | |||
| 10 | W | HW2 | ||||
| 11 | F | |||||
| 12 | M | 2/8 | Decision properties of regular languages | |||
| 13 | W | Equivalence & minimization of DFAs | HW3 | |||
| 14 | F | |||||
| --- | M | 2/15 | President's day (holiday) | |||
| 15 | W | Context free grammars & languages | Chapter 5 | HW3 | ||
| 16 | F | Midterm I | ||||
| 17 | M | 2/22 | ||||
| 18 | W | CFGs... | ||||
| 19 | F | PDAs | Chapter 6 | |||
| 20 | M | 3/1 | HW4 | |||
| 21 | W | D-PDAs | ||||
| 22 | F | |||||
| 23 | M | 3/8 | CFL properties: simplification, normal forms | Chapter 7 | HW4 | |
| 24 | W | HW5 | ||||
| 25 | F | |||||
| --- | M | 3/15 | Spring Break (no classes) | |||
| --- | W | |||||
| --- | F | |||||
| 26 | M | 3/22 | Pumping Lemma for CFLs | |||
| 27 | W | HW5 | ||||
| 28 | F | HW6 | ||||
| 29 | M | 3/29 | ||||
| 30 | W | Closure properties for CFL | ||||
| 31 | F | Turing machines | Chapter 8 | HW6 | ||
| 32 | M | 4/5 | CFL review (HW 5 & 6 ) | |||
| 33 | W | Midterm II review | ||||
| 34 | F | Midterm II | ||||
| 35 | M | 4/12 | Turing machines & extensions, RE languages ... | HW7 | ||
| 36 | W | |||||
| 37 | F | |||||
| 38 | M | 4/19 | Undecidability, diagonalization, problem reduction | Chapter 9 | HW7 | HW8 |
| 39 | W | |||||
| 40 | F | |||||
| 41 | M | 4/26 | Intractable problems | Chapter 10 | HW8 | |
| 42 | W | P & NP, NP-completeness | ||||
| 43 | F | Course & finals review | ||||
| --- | M | 5/3 | FINAL EXAM (Friday, 8-10am, in class) | |||
| --- | W | |||||
| --- | F | |||||