Course Goals
By the end of this course, you will have
developed the following knowledge and skills:
- You will know how to analyze the
powers and limits of various models of computation.
- You will learn and understand several standard proof
techniques, including induction, contradiction, and
diagonalization.
- You will be able to identify problems that are
computationally intractable and argue why these problems might
be hard to solve efficiently.
Above all, the goal of this course is to instill a deep
understanding
of the
limits of computation, and how to think about these
in a thorough and systemic way.