Readings are in Sipser's Introduction to the Theory of Computation, 2nd ed. unless otherwise specified.
#  Day  Date  Topic & Lecture Notes  Readings  Other Handouts  Problem Sets CS121 
Problem Sets CSCI E121 
1  Tu  Sept. 2  Introduction and Overview  Preface  
Unit 1: Finite Automata


2  Th  Sept. 4 
Strings, Languages, 
Ch. 0  
3  Tu  Sept. 9  Finite Automata  Sec. 1.11.2 

PS 0 due 

4  Th  Sept. 11  NFAs vs. DFAs, Closure Properties  Sec 1.11.2  PS 0 due (Fri) 

5  Tu  Sept. 16  Regular Expressions  Sec 1.3 
PS 1 due 

6  Th  Sept. 18  Countability and Uncountaibility  Sec 1.3, Sec 4.2 (pp. 174178) 
PS 1 due (Fri) 

7  Tu  Sept. 23  The Pumping Lemma and Nonregular languages 
Sec 4.2 (pp. 174178), Sec. 1.4 

PS 2 due 

8  Th  Sept. 25  DFA Minimization Context Free Grammars 
Sec. 1.4  PS 2 due (Fri)  
Unit 2: ContextFree Languages


9  Tu  Sept. 30  Ambiguity of Contextfree Grammars Pushdown Automata 
Sec. 2.1 

PS 3 due 

10  Th  Oct. 2  Problem solving session 
Sec. 2.2  PS 3 due (Fri)  
11  Tu  Oct. 7  CFGs vs. PDAs, NonCF Languages  Sec. 2.2, 2.3 

PS 4 due 

12  Th  Oct. 9  CF Recognition  Sec. 2.1  PS 4 due (Fri)  
Unit 3: Computability


13  Tu  Oct. 14  CFL wrapup Hilbert and Turing 
Sec. 3.1  
Th  Oct. 16 
Midterm Examination on Material thru Oct. 10


14  Tu  Oct. 21 
Turing Machines and 
Sec. 3.2, 3.3 
PS 5 due 

15  Th  Oct. 23  Recognizability & Decidability  Sec. 3.2, 3.3, 4.1  PS 5 due (Fri)  
16  Tu  Oct. 28  Turing's Theorem  Sec. 4.1, 4.2 
PS 6 due 

17  Th  Oct. 30  Reducibility  Sec. 4.2, 5.1  PS 6 due (Fri)  
18  Tu  Nov. 4  Partial Recursive Functions, Undecidable questions 
Sec. 5.1, 5.3 
PS 7 due 

Unit 4: Computational Complexity


19  Th  Nov. 6  Computational Complexity  Sec. 7.1 
PS 7 due (Fri) 

20  Tu  Nov. 11  Polynomial Time  Sec. 7.2  PS 8 due 

21  Th  Nov. 13  NP  Sec. 7.3  PS 8 due (Fri)  
22  Tu  Nov. 18  P vs. NP, NPcompleteness  Sec. 7.4, 7.5 


23  Th  Nov. 20  More NPcompleteness  Sec. 7.5  
24  Tu  Nov. 25 
CookLevin and More on NP 
Sec. 7.4, 10.4  
Th  Nov. 27 
NO CLASS  THANKSGIVING 

25  Tu  Dec. 2 
Glimpses Beyond & Conclusions 
Sec. 10.4 
PS 9 due (Tuesday, no late date) 
PS9 due (Tuesday)  
TBD  Review Section 


TBD 
Final Examination 2013 Final Exam and Solutions 