Coursera

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them (Coursera)

Offered by Stanford University,
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them (Coursera)

The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

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

Course 4 of 4 in the Algorithms Specialization.

Syllabus

WEEK 1: The Bellman-Ford algorithm; all-pairs shortest paths.
WEEK 2: NP-complete problems and exact algorithms for them.
WEEK 3: Approximation algorithms for NP-complete problems.
WEEK 4: Local search algorithms for NP-complete problems; the wider world of algorithms.

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

Related Courses

Java Programming: Arrays, Lists, and Structured Data (Coursera) Coursera
Duke University

Java Programming: Arrays, Lists, and Structured Data (Coursera)

CS: Software Engineering CS: Programming

Build on the software engineering skills you learned in “Java Programming: Solving Problems with Software” by learning new data structures. Use these data structures to build more complex programs that use Java’s object-oriented features. At the end of the course you will write an encryption program and a program to break your encryption algorithm.

Nov 2nd 2026
4 Weeks
Programming Java Cryptography
Details
Algorithmic Thinking (Part 1) (Coursera) Coursera
Rice University

Algorithmic Thinking (Part 1) (Coursera)

CS: Theory

Experienced Computer Scientists analyze and solve computational problems at a level of abstraction that is beyond that of any particular programming language. This two-part class is designed to train students in the mathematical concepts and process of "Algorithmic Thinking", allowing them to build simpler, more efficient solutions to computational problems.

Nov 2nd 2026
4 Weeks
Python Computing Algorithms
Details
Comparing Genes, Proteins, and Genomes (Bioinformatics III) (Coursera) Coursera
University of California, San Diego

Comparing Genes, Proteins, and Genomes (Bioinformatics III) (Coursera)

Sci: Biology & Life Sciences Health & Society

Once we have sequenced genomes in the previous course, we would like to compare them to determine how species have evolved and what makes them different. In the first half of the course, we will compare two short biological sequences, such as genes (i.e., short sequences of DNA) or proteins. We will encounter a powerful algorithmic tool called dynamic programming that will help us determine the number of mutations that have separated the two genes/proteins.

Nov 9th 2026
5-12 Weeks
Genes DNA Genomes
Details
Object Oriented Programming in Java (Coursera) Coursera
University of California, San Diego

Object Oriented Programming in Java (Coursera)

CS: Software Engineering CS: Programming

Welcome to our course on Object Oriented Programming in Java using data visualization. People come to this course with many different goals -- and we are really excited to work with all of you! Some of you want to be professional software developers, others want to improve your programming skills to implement that cool personal project that you’ve been thinking about, while others of you might not yet know why you’re here and are trying to figure out what this course is all about.

Nov 2nd 2026
5-12 Weeks
Programming Java Algorithms
Details
Machine Learning (Coursera) Coursera
Stanford University

Machine Learning (Coursera)

Statistics & Data Analysis Data Science

Machine learning is the science of getting computers to act without being explicitly programmed. In the past decade, machine learning has given us self-driving cars, practical speech recognition, effective web search, and a vastly improved understanding of the human genome. Machine learning is so pervasive today that you probably use it dozens of times a day without knowing it. Many researchers also think it is the best way to make progress towards human-level AI. In this class, you will learn about the most effective machine learning techniques, and gain practice implementing them and getting them to work for yourself. More importantly, you'll learn about not only the theoretical underpinnings of learning, but also gain the practical know-how needed to quickly and powerfully apply these techniques to new problems.

Nov 2nd 2026
5-12 Weeks
Artificial Intelligence MATLAB Algorithms
Details
Information Theory (Coursera) Coursera
The Chinese University of Hong Kong

Information Theory (Coursera)

CS: Information & Technology

At the completion of this course, the student should be able to: demonstrate knowledge and understanding of the fundamentals of information theory; appreciate the notion of fundamental limits in communication systems and more generally all systems; develop deeper understanding of communication systems; apply the concepts of information theory to various disciplines in information science.

Nov 2nd 2026
13-24 Weeks
Math Network Algorithms
Details
Digital Signal Processing 4: Applications (Coursera) Coursera
École Polytechnique Fédérale de Lausanne

Digital Signal Processing 4: Applications (Coursera)

Engineering Sci: Physics

Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By reworking the principles of electronics, telecommunication and computer science into a unifying paradigm, DSP is a the heart of the digital revolution that brought us CDs, DVDs, MP3 players, mobile phones and countless other devices.

Nov 9th 2026
3 Weeks
Algorithms DSP Signal Processing
Details
Approximation Algorithms (Coursera) Coursera
EIT Digital

Approximation Algorithms (Coursera)

Computer Science

Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example because the problems are NP-hard. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. These techniques apply when we don't require the optimal solution to certain problems, but an approximation that is close to the optimal solution. We will see how to efficiently find such approximations.

Nov 13th 2026
4 Weeks
Algorithms Approximation Algorithms LP Relaxation
Details
Algorithms, Part I (Coursera) Coursera
Princeton University

Algorithms, Part I (Coursera)

CS: Software Engineering CS: Theory

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.

Nov 16th 2026
5-12 Weeks
Programming Java Algorithms
Details