Course outline, tentative:

• Introduction, sets, defining computation. (4-5 classes)
  • Class 1: Introduction. —📖Barak, Sec 0.
  • Class 2: Definitions. —📖Barak, Sec 1.
  • Class 3: Sets, numbers, strings. —📖Barak, Sec 2.
  • Class 4: Cantor’s theorem, countable and uncountable, functions. —📖Barak, Sec 2.4.
  • Class 5: Cantor’s Theorem, computation. —📖Barak, Sec 3.

(Jan 27)

• Boolean circuits, universal circuits, and circuit complexity. (5-6 classes, announcements)
  • Class 6: Computation models, universality. —📖Barak, Sec 4.
  • Class 7: Universality, circuit size. –📖Barak, Sec 4.6.
  • Class 8: Circuits vs functions, program as data. –📖Barak, Sec 5.
  • Class 9: Lower bound on circuit size. –📖Barak, Sec 5.2
  • Class 10: Circuit size hierarchy. –📖Barak, Sec 5.2.1
  • Class 11: Universal circuit. –📖Barak, Sec 5.4

(Feb 17)

• Finite automata, regular expression. (6 classes, announcements)
  • Class 11: Function with infinite domains, finite automata. –📖Barak, Sec 6
  • Class 12: Regular expressions. –📖Barak, Sec 6.
  • Class 13: Evaluating regular expressions. –📖Barak, Sec 6.3-6.4.
  • Class 14: Limitations of regular expressions. –📖Barak, Sec 6.5
  • Class 15: DFA is computable by regular expressions. –📖Barak, Sec 6.4.2
  • Class 16: Regular expressions is computable by DFA. –📖Sipser, Introduction to the Theory of Computation, Sec 1.2-1.3, Theorem 1.39 and “closure under the regular operations”

(Mar 17)

• 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)