IMPORTANT NOTE: The following schedule represents my current best guess concerning due dates (and everything else). I am providing this information to give you a general idea of the pace and timing of the class. THESE DATES MAY CHANGE. Please don't depend on this schedule in purchasing airline tickets or making other irrevocable scheduling decisions without consulting me first.

 DAY CLASS READING Assign. Out Assign. Due Part One: Automata and Languages M1 IntroductionSyllabusLanguages 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 HW3 F3 Exam IDFAs, NFAs, REs, and regular languages HW3 M4 Context Free Grammars Regular Grammars Chapter 2.1 HW 2 W4 Chomsky Normal Form Chapter 2.2 F4 Pumping Lemma for grammars Finish Chapter 2 M5 Push-down Automata Read Section 2.2 W5 CFG and push-down AutomatasContinued F5 Quick Exam IIFinish Part One Part Two: Computability Theory M6 Church-Turing ThesisTuring machines Chapter 3.1 W6 Turing Maching Labs HW4 from class is now part of TM Lab TM Labs F6 Variants of Turing MachinesAlgorithmsHilbert's Problems Chapter 3.2, 3.3 M7 Decidable Languages Chapter 4.1 W7 UndecidabilityThe Halting Problem Chapter 4.2 F7 Turing recognizable languages M8 Advanced Topics in Computability Theory W8 TBA due to DOGLExam III review F8 Exam III rescheduled due to DOGL Part Three: Complexity Theory M9 Measuring ComplexityThe Class P Chapter 7.1, 7.2 W9 The Class NPThe question Chapter 7.3 F9 NP-completenessNP-complete problems Karp's 21 NPC ProblemsChapter 74., 75 M10 MEMORIAL DAY W10 Review for Exam IIIAttendance Exam Course Review F10 Review for FinalTBA Course Review All work due M11 Monday, 6/5, 8:30 am to 11:00 am Final Exam