NP-Complete Problems

Provided by The University of California, San Diego (UCSanDiegoX)
Learn
Free
Upgrade
$150 USD

Intermediate
See prerequisites

Learn about NP-complete problems, known as hard problems that can’t be solved efficiently, and practice solving them using algorithmic techniques.

Course Format:Instructor-Led
Start Date:Mar 23, 2019

What you will 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

Overview

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

Before you start

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

  • Instructor-Led: course contains assignments and exams that have specific due dates, and you complete the course within a defined time period.
  • Course ends: Mar 23, 2019
Of all edX learners:
73% are employed
Of all edX learners:
45% have children
Based on internal survey results
301,095 people are learning on edX today