• Length:
    3 Weeks
  • Effort:
    8–10 hours per week
  • Price:

    FREE
    Add a Verified Certificate for $150 USD

  • Institution
  • Subject:
  • Level:
    Intermediate
  • Language:
    English
  • Video Transcript:
    English

Prerequisites

Basic knowledge of at least one programming language and material of the Algorithmic ToolboxData Structures and Algorithms on Graphs classes.

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:

  • SAT-solvers
  • Approximate algorithms
  • Special cases of NP-hard problems
  • Heuristic algorithms

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

Daniel Kane
Assistant Professor, Computer Science and Engineering & Dept. of Mathematics
UC San Diego
Alexander S. Kulikov
Visiting Professor
UC San Diego

Pursue a Verified Certificate to highlight the knowledge and skills you gain $150.00

View a PDF of a sample edX certificate
  • Official and Verified

    Receive an instructor-signed certificate with the institution's logo to verify your achievement and increase your job prospects

  • Easily Shareable

    Add the certificate to your CV or resume, or post it directly on LinkedIn

  • Proven Motivator

    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