DAY  CLASS  READING  Assign. Out  Assign. Due 
Part One: Automata and Languages  
M1  Introduction Syllabus Languages and JFLAP 
Chapter 0, Chapter 1.1 
HW0, HW1  
W1  Finite Automata and DFAs  Chapter 1.2  HW2  
F1  DFA Practice  Chapter 1.3  HW0  
M2  Nondeterminism and NFAs  Chapter
1.3 
HW3  HW1 
W2  Regular Expressions  Chapter 2.1 


F2  Equivalence of DFAs, NFAs, Regular Expressions, and Regular Langages  Chapter 2.2 and 2.3  HW 2  
M3  TBA  
W3  TBA  
F3  Exam I DFAs, NFAs, REs, and regular languages 
HW3  
M4  Context Free
Grammars Regular Grammars 
Chapter 2.1  
W4  Chomsky Normal Form  Chapter 2.2  
F4  Pumping Lemma for grammars  Finish Chapter 2  
M5  Pushdown Automata  Read Section 2.2  
W5  CFG and
pushdown Automatas Continued 

F5  Quick Exam
II Finish Part One 

Part Two: Computability Theory  
M6  ChurchTuring
Thesis Turing machines 
Chapter 3.1  
W6  Turing Maching Labs  HW4 from class is now part of TM Lab  TM Labs  
F6  Variants of Turing
Machines Algorithms Hilbert's Problems 
Chapter 3.2, 3.3  
M7  Decidable Languages  Chapter 4.1  
W7  Undecidability The Halting Problem 
Chapter 4.2  
F7  Turing recognizable languages  
M8  Advanced Topics in Computability Theory  
W8  TBA due to
DOGL 

F8  Exam III rescheduled due to DOGL  
Part Three: Complexity Theory  
M9  Measuring
Complexity The Class P 
Chapter 7.1, 7.2  
W9  The
Class NP The question 
Chapter 7.3  
F9  NPcompleteness NPcomplete problems 
Karp's 21 NPC
Problems Chapter 74., 75 

M10  MEMORIAL DAY  
W10  Review for Exam III Attendance Exam 
Course Review  
F10  Course Review  All work due 

M11  Monday, 6/5, 8:30 am to
11:00 am Final Exam 