Course outline (updated Mar 2, 2026):

• Sets and Cardinality. (4-5 classes)
  • Class 0: Introduction. —📖Barak, Sec 0.
  • Class 1: Definitions. —📖Barak, Sec 1.
  • Class 2: Cardinality. —📖Barak, Sec 2.
  • Class 3: Infinity. —📖Barak, Sec 2.
  • Class 4: Cantor’s theorem. Finite Automata. — 📖Barak, Sec 2, 📖Barak, Sec 6.
• Regular Functions. (5-6 classes)
  • Class 5: Regular Expressions. — 📖Barak, Sec 6.
  • Class 6: Regular Expressions vs DFA — 📖Barak, Sec 6.
  • Class 7: DFA to Regular Expressions. — 📖Barak, Sec 6.4.2
  • Class 8: Non-deterministic Finite Automata. — [📖Sipser, Sec 1.2]
  • Class 9: NFA to DFA. — 📖Sipser, Introduction to the Theory of Computation, Sec 1.2-1.3, Theorem 1.39 and “closure under the regular operations”
• Circuits. (4-5 classes)
  • Class 10: Universal gates. — 📖Barak, Sec 4.6.
  • Class 11: Non-universal gates, complexity. — 📖Barak, Sec 4.6.
  • Class 12: Program as Data. — 📖Barak, Sec 5.
  • Class 13: Circuit Size Hierarchy. — 📖Barak, Sec 5.2.1.

Course outline, tentative:

(Mar 10)

• Turing machines, computability. (6 classes, announcements)
  • Class 17: Turing machines. –📖Barak, Sec 7.1.
  • Class 18: Computability. –📖Barak, Sec 7.2.
  • Class 19: Universal Turing Machines and Uncomputability. –📖Barak, Sec 9.1-9.3.
  • Class 20: Halting problem, and reduction. –📖Barak, Sec 9.3-9.4.
  • Class 21: Kolmogorov Complexity. –Notes by Resch @ CMU.
  • Class 22: Rice’s Theorem. –📖Barak, Sec 9.5.

(Apr 7)

• Complexity, completeness, NP. (5 classes)
  • Class 23: Complexity, and class P. –📖Barak, Sec 13.1-13.2.
  • Class 24: Reductions, and class NP. –📖Barak, Sec 12.1-12.2, 15.1.
  • Class 25: P vs NP vs EXP, NP-Complete. –📖Barak, Sec 15.1.2, 15.2.
  • Class 26: Cook-Levin Theorem. –📖Barak, Sec 15.3-15.6.
  • Class 27: Reductions, Review, and Gödel’s Incompleteness. –📖Barak, Sec 14.5, 11.1-11.2.

(Apr 28)