Course outline, tentative:

• Introduction, sets, defining computation. (4-5 classes, announcements)
  • Class 1: Introduction. Slides. —📖Barak, Sec 0.
  • Class 2: Definitions. Slides. —📖Barak, Sec 1. —🏠PS1.
  • Class 3: Sets, numbers, strings. Slides. —📖Barak, Sec 2.
  • Class 4: Cantor’s theorem, countable and uncountable, functions. Slides. —📖Barak, Sec 2.4. —🏠PS2.
  • Class 5: Cantor’s Theorem, computation. Slides. —📖Barak, Sec 3.
• Boolean circuits, universal circuits, and circuit complexity. (5-6 classes, announcements)
  • Class 6: Computation models, universality. Slides. —📖Barak, Sec 4. —🏠PS3.
  • Class 7: Universality, circuit size. Slides. –📖Barak, Sec 4.6.
  • Class 8: Circuits vs functions, program as data. Slides. –📖Barak, Sec 5. —🏠PS4.
  • Class 9: Lower bound on circuit size. Slides. –📖Barak, Sec 5.2
  • Class 10: Circuit size hierarchy. Slides. –📖Barak, Sec 5.2.1
  • Class 11: Universal circuit. Slides. –📖Barak, Sec 5.4
• Finite automata, regular expression. (6 classes, announcements)
  • Class 11: Function with infinite domains, finite automata. –📖Barak, Sec 6
  • Class 12: Regular expressions. Slides. –📖Barak, Sec 6. —🏠PS5.
  • Class 13: Evaluating regular expressions. Slides. –📖Barak, Sec 6.3-6.4. —🏠PS6.
  • Class 14: Limitations of regular expressions. –📖Barak, Sec 6.5
  • Midterm, March 6.
  • 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”
• Turing machines, computability. (6 classes, announcements)
  • Class 17: Turing machines. –📖Barak, Sec 7.1. —🏠PS7.
  • Class 18: Computability. –📖Barak, Sec 7.2. —🏠PS8.
  • 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. —🏠PS9.
  • Class 21: Kolmogorov Complexity. –Notes by Resch @ CMU.
  • Class 22: Rice’s Theorem. –📖Barak, Sec 9.5.
• Complexity, completeness, NP. (5 classes)
  • Class 23: Complexity, and class P. –📖Barak, Sec 13.1-13.2. —🏠PS10.
  • 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.

Meeting dates based on UVA academic calendar (please refer to the Google calendar for updates):

• Week 1: Jan 14, 16
• Week 2: Jan 21, 23
• Week 3: Jan 28, 30
• Week 4: Feb 4, 6
• Week 5: Feb 11, 13
• Week 6: Feb 18, 20
• Week 7: Feb 25, 27
• Week 8: Mar 4, 6 (Mid term)
• Week 9: Mar 18, 20
• Week 10: Mar 25, 27
• Week 11: Apr 1, 3
• Week 12: Apr 8, 10
• Week 13: Apr 15, 17
• Week 14: Apr 22, 24
• Week 15: Apr 29
• May 2 (Final)