Overview
-
This class teaches you about basic concepts in theoretical computer science -- such as NP-completeness -- and what they imply for solving tough algorithmic problems.
Syllabus
-
- Challenging Problems
- An introduction to tough problems and their analysis.
- Understanding Hardness
- What we mean when a problem is "hard" and the concept of NP-completeness.
- Showing Hardness
- Tools to let you recognize and prove that a problem is hard.
- Intelligent Force
- Smart techniques to solve problems that should – theoretically – be impossible to solve.
- Sloppy Solutions
- Gaining speed by accepting approximate solutions.
- Poking Around
- Why randomness can be of help – sometimes. An introduction to complexity classes.
- Ultimate Limits
- Problems that no computer can ever solve. In theory.
