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

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.

Jun 26th 2026
4 Weeks
Algorithms Approximation Algorithms LP Relaxation
Details
Delivery Problem (Coursera) Coursera
University of California, San Diego,Higher School of Economics - HSE University

Delivery Problem (Coursera)

CS: Software Engineering CS: Theory

We’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem. The goal in this problem is to visit all the given places as quickly as possible. How to find an optimal solution to this problem quickly? We still don’t have provably efficient algorithms for this difficult computational problem and this is the essence of the P versus NP problem, the most important open question in Computer Science.

Jun 22nd 2026
3 Weeks
Probability Combinatorics Algorithms
Details
Algorithms on Graphs (Coursera) Coursera
University of California, San Diego,Higher School of Economics - HSE University

Algorithms on Graphs (Coursera)

CS: Software Engineering CS: Theory

If you have ever used a navigation service to find optimal route and estimate time to destination, you've used algorithms on graphs. Graphs arise in various real-world situations as there are road networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect set of computers into a network or efficient algorithm to automatically find communities and opinion leaders in Facebook, you're going to work with graphs and algorithms on graphs.

Jun 22nd 2026
5-12 Weeks
Algorithms Data Structures Graphs
Details
Big Data Analysis with Scala and Spark (Coursera) Coursera
École Polytechnique Fédérale de Lausanne

Big Data Analysis with Scala and Spark (Coursera)

CS: Theory CS: Programming

Manipulating big data distributed over a cluster using functional concepts is rampant in industry, and is arguably one of the first widespread industrial uses of functional ideas. This is evidenced by the popularity of MapReduce and Hadoop, and most recently Apache Spark, a fast, in-memory distributed collections framework written in Scala. In this course, we'll see how the data parallel paradigm can be extended to the distributed case, using Spark throughout.

Jun 22nd 2026
4 Weeks
Programming Algorithms SQL
Details
Algorithmic Toolbox (Coursera) Coursera
University of California, San Diego,Higher School of Economics - HSE University

Algorithmic Toolbox (Coursera)

CS: Software Engineering CS: Theory

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

Jun 22nd 2026
5-12 Weeks
Algorithms Debugging Data Structures
Details
Mastering the Software Engineering Interview (Coursera) Coursera
University of California, San Diego

Mastering the Software Engineering Interview (Coursera)

CS: Software Engineering

You’ve hit a major milestone as a computer scientist and are becoming a capable programmer. You now know how to solve problems, write algorithms, and analyze solutions; and you have a wealth of tools (like data structures) at your disposal. You may now be ready for an internship or (possibly) an entry-level software engineering job. But can you land the internship/job? It depends in part on how well you can solve new technical problems and communicate during interviews. How can you get better at this? Practice!

Jun 22nd 2026
4 Weeks
Algorithms Object-Oriented Software Engineering
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.

Jun 22nd 2026
5-12 Weeks
Genes DNA Genomes
Details
Packet Switching Networks and Algorithms (Coursera) Coursera
University of Colorado System

Packet Switching Networks and Algorithms (Coursera)

Security & Networking

In this course, we deal with the general issues regarding packet switching networks. We discuss packet networks from two perspectives. One perspective involves external view of the network, and is concerned with services that the network provides to the transport layer that operates above it at the end systems. The second perspective is concerned with the internal operation of a network, including approaches directing information across the network, addressing and routing procedures, as well as congestion control inside the network.

Jun 22nd 2026
5-12 Weeks
Algorithms Networks Computer Science
Details
Data Structures (Coursera) Coursera
University of California, San Diego,Higher School of Economics - HSE University

Data Structures (Coursera)

CS: Software Engineering CS: Theory

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments.

Jun 22nd 2026
5-12 Weeks
Algorithms Data Structures Priority Queues
Details
Data Manipulation at Scale: Systems and Algorithms (Coursera) Coursera
University of Washington

Data Manipulation at Scale: Systems and Algorithms (Coursera)

Statistics & Data Analysis Data Science

Data analysis has replaced data acquisition as the bottleneck to evidence-based decision making --- we are drowning in it. Extracting knowledge from large, heterogeneous, and noisy datasets requires not only powerful computing resources, but the programming abstractions to use them effectively. The abstractions that emerged in the last decade blend ideas from parallel databases, distributed systems, and programming languages to create a new class of scalable data analytics platforms that form the foundation for data science at realistic scales.

Jun 22nd 2026
4 Weeks
Algebra Algorithms Databases
Details