Course Schedule and Slides

Course Schedule and Slides (subject to change)


Lec. Date Topics (with PDFs of lecture slides, if applicable) Required Reading Homeworks & Milestones
1 1/19 Course Overview; Introduction to Finite Automata (PDF2up, PDF)
Sipser Ch. 0, 1.1  
2 1/24 Finite Automata: DFAs and NFAs (PDF2up, PDF)
Sipser 1.1, 1.2 HW 1 out
3 1/26 Equivalence of DFAs and NFAs, closure of regular operations (PDF2up, PDF)
Sipser 1.2  
4 1/31 Regular expressions and equivalence with finite automata (PDF2up, PDF)
Sipser 1.3 HW 1 due; HW 2 out
5 2/2 Pumping lemma and non-regular languages Sipser 1.4  
6 2/7 Minimization of DFAs; the Myhill-Nerode theorem (PDF2up, PDF)
Handout HW 2 due; HW 3 out
7 2/9 Context-free languages: introduction (no slides) Sipser 2.1  

2/14 No lecture. Makeup lecture on 2/22
 

2/16 No lecture.
 
  2/21 Holiday, no lecture  
8 2/22 (4-5 pm, in 285 Cory) Pushdown automata; equivalence with CFL  (PDF2up, PDF)
Sipser 2.2 HW 3 due
HW 4 out
9 2/23 PDA-CFL equivalence; Pumping lemma for CFLs (PDF2up, PDF)
Sipser 2.3  
10 2/28 Examples of non-CFLs; Context-sensitive languages; the Chomsky hierarchy (PDF) Sipser 2.3
11 3/2  Turing machines; the Church-Turing thesis Sipser 3.1, 3.3  HW 4 due
HW 5 out
12 3/7 No lecture -- midterm
Midterm
13 3/9 TM examples and TM variants Sipser 3.2
14 3/14 Decidable languages; Diagonalization; The Halting Problem Sipser 4.1 and 4.2 HW 5 due
HW 6 out
15 3/16 Reductions between problems; mapping reducibility Sipser 5.1, 5.3
  3/21 Spring break    
  3/23 Spring break    
16 3/28 Time complexity; The class P Sipser 7.1, 7.2 HW 6 due
HW 7 out
17 3/30 The classes NP and co-NP; Examples; Polynomial-time reductions Sipser 7.3, 7.4  
18 4/4 NP-completeness; examples Sipser 7.4, 7.5 HW 7 due; HW 8 out
19 4/6 review of reductions Sipser 7.4
Karp's paper
 
20 4/11 Proof of Cook-Levin theorem
HW 8 due
21 4/13 PSPACE and NPSPACE; Savitch's theorem Sipser 8.1, 8.2 
22 4/18 No lecture -- midterm
Midterm 2 
23 4/20 PSPACE-completeness; The QBF problem Sipser 8.3 HW 9 out
24 4/25 The classes L and NL; Log-space reductions; NL-completeness Sipser 8.4, 8.5  
25 4/27 Finish NL and L.
HW 10 out
  5/2 RRR week    
  5/4 RRR week  
  5/10 Final Exam, 8 - 11 am, in 306 Soda    HW 9 and 10 due;