In your journey through computation, you likely have noticed that many problems can be solved with the same solution through a skill you have honed called abstraction. Through this process, you may have noticed more nuanced connections between problems. Some problems require some translation before being solved using the solution to another problem. Other problems are immune this sort of transformation and feel fundamentally more difficult than others. Some problems feel downright impossible to solve—are they actually impossible?

In this course, we study the theory of computation where we use mathematics to model problems of increasing complexity and study their relationships with each other. By going through this modeling process, we can:

• Deeply understand a problem and its potential corner cases.
• Prove properties of a problem, e.g., the correctness a candidate solutions.
• Reduce a problem to another problem, i.e, formally solve one problem in terms of another.
• Categorize a problem as easier or harder than other problems in a precise way.

By the end of the course, we will explore the limits of computation. Are there problems that are intractable in practice? Are there problems that can provably never have a solution?

Schedule

Date	Topic/Reading	Lab	Deliverables
F 08/27	Introductions
Week 1: Preliminaries
M 08/30	Review of Mathematical Literacy	Interpreting Definitions	Demo #1 out
W 09/01	Constructive and Classical Proof	Formal Proof
F 09/03	Deterministic Finite Automata	DFA Basics
Week 2: Finite Automata
M 09/06	Design with Finite Automata	DFA Design	Demo #2 out Demo #1 due
W 09/08	Nondeterminism	Exploring Nondeterminism
F 09/10	Equivalence of Models	Finding Essence
Week 3: Regularity
M 09/13	Closure Properties	Closure Problems	Demo #3 out Demo #2 due
W 09/15	Regular Expressions	Regular Expressions	Demo #1 revisions due
F 09/17	Analysis of Regular Models	Exploring the Regular Models
Week 4: Beyond Regularity
M 09/20	Irregularity and the Pumping Lemma	Irregularity	Demo #4 out Demo #3 due
W 09/22	Myhill-Nerode Theorem	Applying Myhill-Nerode	Demo #2 revisions due
F 09/24	Context-Free Grammars	Context-free Grammars
Week 5: Turing Machines
M 09/27	Introduction to Turing Machines	Introduction to Turing Machines	Demo #4 due
W 09/29	Variants and The Church-Turing Thesis	Properties and Variants of TMs	Demo #3 revisions due
F 10/01	(No class, LA day!)		LA #1 out
Week 6: Time Complexity
M 10/04	Time Complexity	Time Complexity	Demo #5 out
W 10/06	NP-Completeness	NP-Completeness	Demo #4 revisions due
F 10/08	The Cook-Levine Theorem	The Cook-Levine Theorem
Week 7: NP-Completeness
M 10/11	Mapping Reducibility	Mapping Reducibility	Exploration #1 out Demo #5 due
W 10/13	Classical NP-Complete Problems	More Mapping Reductions
F 10/15	P vs. NP
(Fall break: 10/18 to 10/22)
Week 8: Space Complexity
M 10/25	Space Complexity	Space Complexity	Demo #6 out
W 10/27	Savitchs Theorem	Space Relationships	Demo #5 revisions due
F 10/29	PSPACE and PSPACE-Completeness	PSPACE-Completeness
Week 9: Complexity Wrap-Up
M 11/01	Sublinear Space Complexity	Complements and Complexity	Demo #6 due
W 11/03	Hierarchy Theorems	Complexity Wrap-Up
F 11/05	(No class, LA day!)		LA #2 out
Week 10: Computability
M 11/08	Machine Analysis	Machine Analysis	Demo #7 out
W 11/10	Diagonalization	Diagonalization	Demo #6 revisions due
F 11/12	Undecidability	Undecidability
Week 11: Undecidability
M 11/15	Undecidability Reductions	Machine Behavior Undecidability	Demo #8 out Demo #7 due
W 11/17	The Post-Correspondence Problem	PCP
F 11/19	Rices Theorem	Rices Theorem
Week 12: Computability and Logic
M 11/22	Recursion and Logical Theories	Quine Exploration	Demo #8 due
W 11/24	(No class, pre-Thanksgiving Break!)		Demo #7 revisions due
(Thanksgiving Break: 11/25 and 11/26)
Week 13: Approximation and Probabilistic Computation
M 11/29	Approximate Computing	PTASs	Demo #9 out
W 12/01	Approximation with Linear Programming	Approximation with Linear Programming	Demo #8 revisions due
F 12/03	Hardness of Approximation	Hardness of Approximation
Week 14: The Future of Computation
M 12/06	Solving SAT Efficiently	DPLL	Demo #9 due
W 12/08	The Theory of Computation
F 12/10	(No class, LA day!)		LA #3 out
Finals Week
M 12/13			Exploration #2 out
T 12/14			LA #4 out
W 12/15			Demo #9 revisions due
F 12/17			All remaining work due

Learning Goals

• Learning Assessment 1
  • Represent a problem using a regular model of computation.
  • Prove closure and algorithmic properties of the regular languages.
  • Prove the irregularity of a problem.
  • Represent a problem using a context-free model of computation.
  • Represent a problem using a Turing machine.
  • Prove closure and algorithmic properties of Turing machines.
• Learning Assessment 2
  • Prove that a problem is in a particular time complexity class.
  • Prove that a problem is NP-complete by way of a reduction.
  • Explain the practical ramifications of the P vs. NP problem.
  • Prove that a problem is in a particular space complexity class.
  • Describe the essential charactistics of problems belonging to each of the major complexity classes.
  • Describe the practical relationships between various time and space complexity classes.
• Learning Assessment 3
  • Prove the decidability of a given machine analysis algorithm.
  • Prove the undecidability of a given problem by way of a reduction.
  • Prove the undecidability of a given problem through Rice's Theorem.
  • Describe the practical ramifications of computational undecidability.
  • Describe practical problem solving strategies for dealing with intractable problems.
  • Design and reason about an approximation algorithm to an optimization problem.