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