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.