NP-Complete Problems

Course 4 of 8: MicroMasters® Program in Algorithms and Data Structures 3 Weeks 8 - 10 hours each week recommended

Please select the start dates for your courses below.

Scheduled Start:

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


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

Who can take this course?


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


3 Weeks

Experience Level


Learning Partner

San Diego

Program Type

Advanced Business Harvard X-Series