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
Due on Sunday: Assignment 4 (CFGs)
Reading: Section 2.2
Topics: More CFGs and Pushdown automata
Reading: Sections 2.3 and 3.1
Topics: Finish PDAs, Non-context-free languages, and start of Turing Machines
Due on Sunday: Assignment 5 (PDAs and Non-CFLs)
Reading: Section 3.1 (continued)
Topics: More on TMs: Formal definition and full examples
Reading: Section 3.2
Topics: More TM examples and TM variants – skipped: enumerators and section 3.3
Reading: Section 4.1-4.2
Topics: Decidable languages and start of undecidability
Due on Tuesday: Assignment 6 (TMs, variants, and decidable languages)
Topics: More on undecidability, and review/problem day (chapters 2–4)
Exam 2 (covers chapters 2–4)
Reading: Section 5.1
Topics: Undecidable Problems from Language Theory
Due on Sunday: Assignment 7 (Undecidability)
Topics: Undecidable Problems from Language Theory (continued)
Reading: Section 5.2-5.3
Topics: A simple undecidable problem, and mapping reducibility
Due Friday, April 4: Graduate/honors student project topic selection for Project
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