About this courseSkip About this course
Step into the area of more complex problems and learn advanced algorithms to help solve them.
This course, part of the Algorithms and Data Structures MicroMasters program, discusses inherently hard problems that you will come across in the real-world that do not have a known provably efficient algorithm, known as NP-Complete problems.
You will practice solving large instances of some of these problems despite their hardness using very efficient specialized software and algorithmic techniques including:
- Approximate algorithms
- Special cases of NP-hard problems
- Heuristic algorithms
What you'll learnSkip What you'll learn
- NP-completeness and how to deal with it
- How to approximate algorithms
- How to use heuristic algorithms to solve a problem more quickly when classic methods are too slow
Week 1: NP-Complete Problems
Although many of the algorithms you've learned so far are applied in practice a lot, it turns out that the world is dominated by real-world problems without a known provably efficient algorithm. Many of these problems can be reduced to one of the classical problems called NP-complete problems which either cannot be solved by a polynomial algorithm or solving any one of them would win you a million dollars (see Millenium Prize Problems) and eternal worldwide fame for solving the main problem of computer science called P vs NP. It's good to know this before trying to solve a problem before the tomorrow's deadline :) Although these problems are very unlikely to be solvable efficiently in the nearest future, people always come up with various workarounds. In this module you will study the classical NP-complete problems and the reductions between them. You will also practice solving large instances of some of these problems despite their hardness using very efficient specialized software based on tons of research in the area of NP-complete problems.
Week 2: Coping with NP-completeness: special cases
After the previous module you might be sad: you've just went through 5 courses in Algorithms only to learn that they are not suitable for most real-world problems. However, don't give up yet! People are creative, and they need to solve these problems anyway, so in practice there are often ways to cope with an NP-complete problem at hand. We show that some special cases on NP-complete problems can, in fact, be solved in polynomial time.
Week 3: Coping with NP-completeness: exact and approximate algorithms
We consider exact algorithms that find a solution much faster than the brute force algorithm. We conclude with approximation algorithms that work in polynomial time and find a solution that is close to being optimal.
Meet your instructors
Pursue a Verified Certificate to highlight the knowledge and skills you gain$150 USD
Official and Verified
Receive an instructor-signed certificate with the institution's logo to verify your achievement and increase your job prospects
Add the certificate to your CV or resume, or post it directly on LinkedIn
Give yourself an additional incentive to complete the course
Support our Mission
edX, a non-profit, relies on verified certificates to help fund free education for everyone globally
Who can take this course?
Unfortunately, learners from one or more of the following countries or regions will not be able to register for this course: Iran, Cuba and the Crimea region of Ukraine. While edX has sought licenses from the U.S. Office of Foreign Assets Control (OFAC) to offer our courses to learners in these countries and regions, the licenses we have received are not broad enough to allow us to offer this course in all locations. edX truly regrets that U.S. sanctions prevent us from offering all of our courses to everyone, no matter where they live.