CS/Math 387

Computability and Complexity
Spring 2023

Current week   |   Moodle   |   Course information
Instructor: David Perkinson (schedule)
Text: Introduction to the Theory of Computation, by Michael Sisper.
Course structure: This will be a flipped course based on Sipser's OCW 18.404J course.
Office hours: 10–11 MWF, 3–4 TuTh, or by appointment or drop-in.
Final exam: 9 am–12 pm, Tuesday, May 9, P240A. Review sheet.
Reading Week office hours: Monday 10–noon; Thursday 1:30–3 pm; Friday 10–noon.
Week 1: January 23 - 27
Monday: Introduction. Deterministic finite automata.
Wednesday: Nondeterminism, closure properties, regular expressions and finite automata.
Friday: Watch the first 30 minutes of Lecture 3.
Week 2: January 30 - February 3
Monday: Regular Pumping Lemma, Finite Automata → Regular Expressions, CFGs.
Wednesday: Pushdown Automata, CFG ↔ PDA.
Friday: Today's class will cover material in the previous two lectures.
Week 3: February 6 - 10
Monday: The CF Pumping Lemma, Turing Machines.
Wednesday: TM Variants, the Church-Turing Thesis.
Friday: Today's class will cover material in the previous two lectures.
Week 4: February 13 - 17
Monday: Decision Problems for Automata and Grammars.
Wednesday: Undecidability.
Friday: Today's class will cover material in the previous two lectures.
Week 5: February 20 - 24
Monday: Reducibility.
Wednesday: The Computation History Method.
Friday: Snow day.
Week 6: February 27 - March 3
Monday: Today's class is via Zoom. See the link near the top of our moodle page or in your email. It covers material from last week, making up for the snow day and providing important material for this week's homework.
Wednesday: Time Complexity.
Friday: P and NP, SAT, Poly-time Reducibility. (The lecture numbering skips from 12 to 14 since Sipser's class had a midterm.)
Week 7: March 6 - 10
Monday: NP-Completeness.
Wednesday: Cook-Levin Theorem.
Friday: Today's class will cover material in the previous two lectures.
Spring break: March 13 - 17
No classes this week.

Week 8: March 20 - 24
Monday: Space Complexity, PSPACE, Savitch’s Theorem.
Wednesday: A unusual programming language.
  • Reading: None.
Friday: Midterm
Week 9: March 27 - 31
Monday: PSPACE-Completeness.
Wednesday: Games, Generalized Geography.
Friday: No class today.
Week 10: April 3 - 7
Monday: L and NL, NL = coNL.
Wednesday: Hierarchy Theorems.
Friday: Review of this week's material.
Week 11: April 10 - 14
Monday: Provably Intractable Problems, Oracles.
Wednesday: Probabilistic Computation, BPP.
Friday: Review.
Week 12: April 17 - 21
Monday: Probabilistic Computation (cont.).
Wednesday: Interactive Proof Systems, IP.
Friday: Review
Week 13: April 24 - 28
Monday: coNP ⊆ IP.
Wednesday: Review.
Friday: Final exam review sheet.
The \(\LaTeX\) document preparation system