TENTATIVE SCHEDULE FOR CPT S 317 (Spring 2017)Schedule subject to change as the course progresses

* 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 (IN CLASS) --- 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.