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 nonregular languages 
Sipser 1.4 

6 
2/7 
Minimization of DFAs; the MyhillNerode theorem (PDF2up, PDF)

Handout 
HW 2 due; HW 3 out 
7 
2/9 
Contextfree 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 (45 pm, in 285 Cory) 
Pushdown automata; equivalence with CFL (PDF2up, PDF)

Sipser 2.2 
HW 3 due
HW 4 out 
9 
2/23 
PDACFL equivalence; Pumping lemma for CFLs (PDF2up, PDF)

Sipser 2.3 

10 
2/28 
Examples of nonCFLs; Contextsensitive languages; the Chomsky hierarchy (PDF) 
Sipser 2.3 

11 
3/2 
Turing machines; the ChurchTuring 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 coNP; Examples; Polynomialtime reductions 
Sipser 7.3, 7.4 

18 
4/4 
NPcompleteness; 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 CookLevin 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 
PSPACEcompleteness; The QBF problem 
Sipser 8.3 
HW 9 out 
24 
4/25 
The classes L and NL; Logspace reductions; NLcompleteness 
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; 