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 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
HW3
F3 Exam I
DFAs, 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 Automatas
Continued



F5 Quick Exam II
Finish Part One



Part Two: Computability Theory
M6 Church-Turing 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
Exam III review

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 NP-completeness
NP-complete problems
Karp's 21 NPC Problems
Chapter 74., 75


M10 MEMORIAL DAY

W10 Review for Exam III
Attendance 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