Week #  Lecture #s  Descriptions
 Handouts/Homework

13  
 Final Review
 P, NP, PSPACE, NPSPACE
 
14  
 NO CLASS
 Exam Review, The class P and NP
 
13   
 Exam #3
 15.1a,c, 15.3, 15.7, Exam Review
 
12  
 Reducibility
 No class  Ramsey out sick

 13.1, 13.2, 13.3, 13.5, 13.17 and 14.1, 14.3, 14.6
 No class  Ramsey out sick

11  
n Countable Sets, Diagonalization, Halting Problem
 Librarian's Paradox, Recursive and Recursively Enumerable

 Test Submission, Chapter 12: 12.2, 12.3a, 12.13, 12.15, 12.18, 12.19
 Chapter 11, 11.1, 11.2, 11.3, 11.511.9 (describe algorithms),11.10, 11.11, 11.13ac, 11.14ac, 11.15, 11.17

10  
 Some decidable problems and proofs
 Turing machines and variations
 
9    
8  
 Break
 Church's Thesis, HW Review
 
7  
 Turing Machine, Halting, Nondeterminism, Multiple Tapes
 Pumping Lemma


 Chapter 9: 16,810,12,13,15a,16,17,20

6  
 Chomsky's Normal Form, Pumping Lemma
 Chomsky's Hierarchy, CFG>PDA


 Chapter 8: 14,8,1012 (#6 for EC, but #5 may help)

5   

 ALL Chapter 7 Problems (skip 7.7), Due Thursday 10/2

4  
 ContextFree Grammars
 Pumping Lemma, Closure Properties for Proofs

 All Chapter 6 problems Due Tuesday 9/30 (first T after Exam #1)


3  
 Applications: Bots, Elevators, Automatic Doors
 Pumping Lemma, Closure Properties


 Chapter 4 Homework: All (except 4.6b and 4.6c)

2  
 Regular Languages, Pumping Lemma
 Conversions ( RE>NFA<>DFA>RE )

 Chapter 3: all problems. (except #3 and #16)


1  
 Nondeterminism
 Finite Automata, Regular Expressions

 C2 15, 6 (REs only), 712, 13 (hard), 1417, 18 (e.c.)
 Syllabus  All Chapter 1 Problems.
