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
Due on Sunday: Assignment 1 (Math Background and Proofs)
Reading: Section 1.1
Topics: Deterministic finite automata (DFAs)
Reading: Section 1.2
Topics: Nondeterministic Finite Automata (NFAs)
Due on Sunday: Assignment 2 (DFAs and NFAs)
Reading: Sections 1.3
Topics: Regular expressions
Reading: Sections 1.4
Topics: Non-regular languages (pumping lemma)
Due on Sunday: Assignment 3 (Regular Expressions and Pumping Lemma)
Reading: Section 2.1
Topics: Introduction to Context-Free Grammars
Topics: Review and problem day (chapters 0 and 1)
Exam 1 (covers Chapters 0 and 1)
Reading: Section 2.2
Topics: More CFGs and Pushdown automata
Due on Sunday: Assignment 4 (CFGs and PDAs)
Reading: Section 2.3
Topics: Non-Context-Free Languages
Reading: Section 3.1
Topics: Turing Machines
Due on Sunday: Assignment 5 (Non-CFLs and TMs)
Reading: Section 3.2–3.3
Topics: Variants of Turing Machines, and Algorithms
Reading: Section 4.1
Topics: Decidable Languages
Reading: Section 4.2
Topics: Undecidability
Due on Tuesday: Assignment 6 (TM variants and decidable languages)
Topics: Review and problem day (chapters 2–4)
Exam 2 (covers chapters 2 and 3)
Reading: Section 5.1
Topics: Undecidable Problems from Language Theory
Due on Sunday: Assignment 7 (Undecidability)
Topics: Undecidable Problems from Language Theory (continued)
Graduate/Honors students: Topic selection for Project is due
Reading: Section 5.2-5.3
Topics: A simple undecidable problem, and mapping reducibility
Due on Sunday: Assignment 8 (PCP and mapping reducibility)
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 basics
Due on Sunday: Assignment 9 (Time complexity, P, and NP)
Reading: Sections 7.5
Topics: Cook-Levin Theorem and NP-completeness proofs
Graduate/Honors students: Progress report for Project is due
Reading: Section 7.5 (continued)
Topics: More NP-completeness proofs
Due on Sunday: Assignment 10 (NP completeness proofs)
Reading: Sections 8.1–8.2
Topics: Basics of space complexity and Savitch’s Theorem
Reading: Sections 8.3
Topics: PSPACE-completeness
Due on Sunday: Assignment 11 (Space complexity)
Topics: Catch-up, or class choice topic
Graduate/Honors students: Final report for Project is due
Topics: Class wrap-up and review