Week #
 Description  Files/HW/Links

16 
Final Exams
 
15 
Reading DayReview NPcomplete and problems
 
14 
PSPACE NPSPACE, L, NL, relationshipsPvNP
 
13 
P vs. NP
 
12 
ComplexitySpace Exam 3
 
11 
SpaceReducibility/ReviewReducibility Problems/Rice's Thm
 
10 
ReducibilityRecursive, Recursively Enumerable, TMs, Decidability, etc
 
9 
Halting ProblemCountableTuring Machines/Decidable vs. Recognizable
 
8 
Exam 2 Review
  C13: 1, 2, 3, 5, 8, 17
 C12: 2, 3.a, 7, 13, 15, 18, 19

7 
Turing Machines
 
6 
Pumping LemmaCFG Properties
  C9.1, 9.3, 9.5, 9.9, 9.10, 9.15
 C8.1, 8.10, 8.11

5 
CNF, CFGs, HWCNF PDAs, CFGs, CNF
 
 C7: 7.2, 7.3, 7.6, 7.18 (look at the rest)
 C6: 6.2, 6.5, 6.10, 6.11, 6.17 (look at the rest)

4 
Exam #1Review / Context Free Grammars/Languages
 
3
 ApplicationsClosure PropertiesPumping Lemma
 Chapter 4 Hand In: 1, 2, 3, 5, 8, 11, 12, 13, 14
In C4: Think About: 4, 6, 7, 9, 10, 15, 16, 17

2
 Pumping LemmaConversions,Regular LanguagesConversions (RE>NFA<>DFA>RE)
 Chapter 3: all problems except #3 and 16

1
 NondeterminismRegular ExpressionsAutomata, Finite, Regular Expressions
 Chapter2 problems 15, 6 (REs only), 712, 13(hard),1417,18(e.c) All of chapter 1 Syllabus
