This class teaches you about basic concepts in theoretical computer science -- such as NP-completeness -- and what they imply for solving tough algorithmic problems.
Overview
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.
Taught by
Sebastian Wernicke
Related Courses
Related articles
Reviews
3.0 rating, based on 2 Class Central reviews
-
A good introduction to computational complexity, with some subtle theoretical concepts presented in a clear and amenable way. Stressing the importance of good theoretical foundations and the analysis of algorithms.
-
Pacing of this course is all off. If you're gonna be doing this be prepared for a lot of frustrated evenings and hair-pulling frustration trying to get a grasp on what the lecturer is even trying to tell you.
