TENTATIVE SCHEDULE FOR CPT S 317 (Spring 2017)
* 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 | |||||
| 5 | F | |||||
| 6 | M | 1/23 | Equivalence of DFA & NFA, epsilon transitions | Chapter 3 | HW1 (rubrics) | |
| 7 | W | |||||
| 8 | F | |||||
| 9 | M | 1/30 | Regular expressions | HW1 | HW2 (rubrics) | |
| 10 | W | |||||
| 11 | F | Regular language properties: pumping lemma | Chapter 4 | |
||
| 12 | M | 2/6 | HW2 |
HW3 (rubrics) | ||
| 13 | W | Closure properties | ||||
| 14 | F | |||||
| --- | M | 2/13 | Decision properties of regular languages | |||
| 15 | W | |||||
| 16 | F |
Equivalence
& minimization of DFAs |
HW3 | |||
| 17 | M | 2/20 | President's day (holiday) | |||
| 18 | W |
Midterm I |
||||
| 19 | F | |||||
| 20 | M+ | 2/27 | Instructor
on travel - no class |
|||
| 21 | W+ | TA will discuss midterm test and homework solutions in class. | ||||
| 22 | F | Context Free Grammars | Chapter 5 |
|||
| 23 | M | 3/6 | HW4 (rubrics) | |||
| 24 | W | Chapter 6, 7 | ||||
| 25 | F | |||||
| --- | M | 3/13 | Spring Break (no classes) | |||
| --- | W | |||||
| --- | F | |||||
| 26 | M | 3/20 | PDAs | HW4 |
||
| 27 | W | HW5 (rubrics) | ||||
| 28 | F | CFL properties: simplification, normal forms | ||||
| 29 | M | 3/27 | Pumping Lemma for CFLs | |||
| 30 | W | HW5 |
HW6 (rubrics) | |||
| 31 | F | Closure properties for CFL | Chapter 8 | |||
| 32 | M | 4/3 | Turing machines | |||
| 33 | W | HW6 |
HW7 (rubrics) | |||
| 34 | F | CFL review (HW 4, 5 & 6 ) | ||||
| 35 | M | 4/10 | Midterm II review | |||
| 36 | W |
|
HW7 | |||
| 37 | F | Turing machines & extensions, RE languages ... | Chapter 9 | |||
| 38 | M | 4/17 |
Midterm II |
|||
| 39 | W | Undecidability, diagonalization, problem reduction | HW8 (rubrics) | |||
| 40 | F | |||||
| 41 | M | 4/24 | Intractable problems | Chapter 10 | ||
| 42 | W | P & NP, NP-completeness | HW8 | |||
| 43 | F | Course & finals review | ||||
| --- | M | 5/1 |
FINAL EXAM:
WEDNESDAY, MAY 3, 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. Please look out for announcements regarding class schedule those dates.