The following gives a day-by-day breakdown of topics covered, readings assigned, and assignment handouts/due dates. Each topic includes several required readings that students should read before the topic is discussed in class – always look ahead a few days to see what readings you should be doing.
The schedule in this class is flexible, and past dates will be updated to reflect what was actually covered. Future dates are always tentative and subject to change, and dates more than two week in the future are simply “best guesses” to be updated as the time approaches.
Topics: Class overview and syllabus review; introduction to theory of computing
Reading: Sections 0.1 – 0.2
Topics: Review of mathematical structures
Reading: Sections 0.3 – 0.4
Topics: Review of proof techniques
Reading: Section 1.1
Due: Assignment 1
Topics: Deterministic finite automata (DFAs)
Reading: Section 1.2
Topics: Nondeterministic Finite Automata (NFAs)
Reading: Sections 1.3 – 1.4
Topics: Regular expressions and non-regular languages (pumping lemma) - day 1
Topics: Regular expressions and non-regular languages (pumping lemma) - day 2
Due: Assignment 2
Reading: Section 2.1
Topics: Context-Free Grammars - day 1
Reading: Section 2.1
Topics: Context-Free Grammars - day 2
Topics: Review and problem day (chapters 0 and 1)
Exam 1 (covers Chapters 0 and 1)
Reading: Section 2.2
Topics: Pushdown automata
Reading: Section 2.3
Topics: Non-Context-Free Languages
Due: Assignment 3
Reading: Section 2.4
Topics: Deterministic Context-Free Languages and parsing
Reading: Section 3.1
Topics: Turing Machines
Reading: Section 3.2–3.3
Topics: Variants of Turing Machines, and Algorithms
Due: Assignment 4
Reading: Section 4.1
Topics: Decidable Languages
Reading: Section 4.2
Topics: Undecidability
Topics: Review and problem day (chapters 2 and 3)
Exam 2 (covers chapters 2 and 3)
Reading: Section 5.1
Topics: Undecidable Problems from Language Theory
Reading: Section 5.2-5.3
Topics: A simple undecidable problem, and mapping reducibility
Due: Assignment 5
Reading: Sections 7.1–7.2
Topics: Time complexity and the class P
Reading: Sections 7.3–7.4
Topics: The class NP and NP-completeness
Reading: Section 7.5
Topics: Additional NP-complete problems
Reading: Sections 8.1–8.2
Topics: Basics of space complexity and Savitch’s Theorem
Due: Assignment 6 – due Tuesday, Nov 26
Topics: Catch-up, or class choice topic
Topics: Class wrap-up and review
Friday, December 6, 3:30-6:30