EdX

NP-Complete Problems (edX)

NP-Complete Problems (edX)

Learn about NP-complete problems, known as hard problems that can’t be solved efficiently, and practice solving them using algorithmic techniques. Step into the area of more complex problems and learn advanced algorithms to help solve them.

Class Deals by MOOC List - Click here and see EdX's Active Discounts, Deals, and Promo Codes.

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

Course Syllabus

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.

Prerequisites
Basic knowledge of at least one programming language and material of the Algorithmic Toolbox, Data Structures and Algorithms on Graphs classes.

Go to Class
MOOC List is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Related Courses

Advanced Linear Algebra: Foundations to Frontiers (edX) EdX
University of Texas at Austin,UTAustinX

Advanced Linear Algebra: Foundations to Frontiers (edX)

Learn advanced linear algebra for computing. Linear algebra is one of the fundamental tools for computational and data scientists. In Advanced Linear Algebra: Foundations to Frontiers (ALAFF), you will build your knowledge, understanding, and skills in linear algebra, practical algorithms for matrix computations, and the analysis of the effects of floating-point arithmetic as performed by computers.

Self Paced
Self-Paced
Data Structures & Algorithms I: ArrayLists, LinkedLists, Stacks and Queues (edX) EdX
Georgia Institute of Technology,GTx

Data Structures & Algorithms I: ArrayLists, LinkedLists, Stacks and Queues (edX)

Work with the principles of data storage in Arrays, ArrayLists & LinkedList nodes. Understand their operations and performance with visualizations. Implement low-level linear, linked data structures with recursive methods, and explore their edge cases. Extend these structures to the Abstract Data Types, Stacks, Queues and Deques.

Self Paced
Self-Paced
Aplicaciones de la Teoría de Grafos a la vida real II (edX) EdX
Universitat Politècnica de València,UPValenciaX

Aplicaciones de la Teoría de Grafos a la vida real II (edX)

Aprenderemos a modelizar problemas del mundo real mediante su representación con grafos y a resolverlos mediante sus algoritmos asociados. Este curso trata la Teoría de Grafos desde el punto de vista de la modelización, lo que nos permitirá con posterioridad resolver muchos problemas de diversa índole. Presentaremos ejemplos de los distintos problemas en un contexto real, analizaremos la representación de éstos mediante grafos y veremos los algoritmos necesarios para resolverlos.

Self Paced
Self-Paced
AP Computer Science A: Java Programming Polymorphism and Advanced Data Structures (edX) EdX
Purdue University,PurdueX

AP Computer Science A: Java Programming Polymorphism and Advanced Data Structures (edX)

AP Computer Science A from Purdue University. This computer science course covers advanced OOP strategies, including polymorphism, abstract classes, super keyword, exceptions, generics, sorting and searching algorithms. This course is for anyone interested in taking a first-level computer-programming course, particularly those who attend a school that does not provide a similar class.

This course is archived
5-12 Weeks
CS50's Introduction to Computer Science (edX) EdX
HarvardX,Harvard University

CS50's Introduction to Computer Science (edX)

An introduction to the intellectual enterprises of computer science and the art of programming. This is CS50, Harvard University's introduction to the intellectual enterprises of computer science and the art of programming for majors and non-majors alike, with or without prior programming experience. An entry-level course taught by David J. Malan, CS50 teaches students how to think algorithmically and solve problems efficiently.

Self Paced
Self-Paced
Advanced Bayesian Statistics Using R (edX) EdX
University of Canterbury,UCx

Advanced Bayesian Statistics Using R (edX)

Now that you know the basics of Bayesian inference, dive deeper to explore its richness and flexibility more fully. Let’s take a closer look at modeling latent variables, Bayesian model averaging, generalised linear models, and MCMC methods. Advanced Bayesian Data Analysis Using R is part two of the Bayesian Data Analysis in R professional certificate.

Self Paced
Self-Paced
Advanced Algorithmics and Graph Theory with Python (edX) EdX
Institut Mines-Telecom,IMTx

Advanced Algorithmics and Graph Theory with Python (edX)

Strengthen your skills in algorithmics and graph theory, and gain experience in programming in Python along the way. Algorithmics and programming are fundamental skills for engineering students, data scientists and analysts, computer hobbyists or developers. Learning how to program algorithms can be tedious if you aren’t given an opportunity to immediately practice what you learn. In this course, you won't just focus on theory or study a simple catalog of methods, procedures, and concepts. Instead, you’ll be given a challenge wherein you'll be asked to beat an algorithm we’ve written for you by coming up with your own clever solution.

Sep 4th 2023
5-12 Weeks
Data Structures & Algorithms III: AVL and 2-4 Trees, Divide and Conquer Algorithms (edX) EdX
Georgia Institute of Technology,GTx

Data Structures & Algorithms III: AVL and 2-4 Trees, Divide and Conquer Algorithms (edX)

Learn more complex tree data structures, AVL and (2-4) trees. Investigate the balancing techniques found in both tree types. Implement these techniques in AVL operations. Explore sorting algorithms with simple iterative sorts, followed by Divide and Conquer algorithms. Use the course visualizations to understand the performance.

Self Paced
Self-Paced
Fundamentals of Python (edX) EdX
SDA_Bocconi,SDA Bocconi School of Management

Fundamentals of Python (edX)

We will equip you with everything you need to properly start using Python in your daily work activities. You will learn how to install Python and work with it through different graphical front-ends. You will then learn how to define objects and how to recognize different characteristics and functionalities. Finally, you will learn how to make Python execute a series of instructions in a sequential order through loops, as well as how to write your own functions.

Self Paced
Self-Paced