Intro to Theoretical Computer Science

This class teaches you about basic concepts in theoretical computer science -- such as NP-completeness -- and what they imply for solving tough algorithmic problems.

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