Coursera

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

Offered by Stanford University,

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

Coursera

University of Michigan

Python Data Structures (Coursera)

CS: Software Engineering CS: Programming

This course will introduce the core data structures of the Python programming language. We will move past the basics of procedural programming and explore how we can use the Python built-in data structures such as lists, dictionaries, and tuples to perform increasingly complex data analysis. This course will cover Chapters 6-10 of the textbook “Python for Everybody”. This course covers Python 3.

Sep 7th 2026

5-12 Weeks

Programming Python Semantics

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.

Sep 7th 2026

4 Weeks

Programming Java Cryptography

Coursera

University of Leeds

An Introduction to Cryptography (Coursera)

Computer Science

Cryptography is an essential part of secure but accessible communication that's critical for our everyday life and organisations use it to protect their privacy and keep their conversations and data confidential. This course provides a comprehensive introduction to the fascinating world of cryptography, covering both historical cyphers and modern-day cryptographic techniques.

Sep 21st 2026

2 Weeks

Cryptography Algorithms Encryption

Coursera

University of Cape Town

Julia Scientific Programming (Coursera)

Statistics & Data Analysis Data Science

This four-module course introduces users to Julia as a first language. Julia is a high-level, high-performance dynamic programming language developed specifically for scientific computing. This language will be particularly useful for applications in physics, chemistry, astronomy, engineering, data science, bioinformatics and many more.

Sep 14th 2026

4 Weeks

IPython Data Analysis Computer Programming

Coursera

University of Illinois at Urbana-Champaign

Cloud Computing Concepts: Part 2 (Coursera)

CS: Software Engineering CS: Theory

Cloud computing systems today, whether open-source or used inside companies, are built using a common set of core techniques, algorithms, and design philosophies—all centered around distributed systems. Learn about such fundamental distributed computing "concepts" for cloud computing. Some of these concepts include: Clouds, MapReduce, key-value stores, Classical precursors, Widely-used algorithms, Classical algorithms, Scalability, Trending areas, And more!

Sep 7th 2026

5-12 Weeks

Programming Cloud Algorithms

Coursera

Rice University

Algorithmic Thinking (Part 2) (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.

Sep 7th 2026

4 Weeks

Python Computing Algorithms

Coursera

University of Illinois at Urbana-Champaign

VLSI CAD Part I: Logic (Coursera)

CS: Software Engineering CS: Theory

A modern VLSI chip has a zillion parts -- logic, control, memory, interconnect, etc. How do we design these complex chips? Answer: CAD software tools. Learn how to build thesA modern VLSI chip is a remarkably complex beast: billions of transistors, millions of logic gates deployed for computation and control, big blocks of memory, embedded blocks of pre-designed functions designed by third parties (called “intellectual property” or IP blocks). How do people manage to design these complicated chips? Answer: a sequence of computer aided design (CAD) tools takes an abstract description of the chip, and refines it step-wise to a final design.

Sep 21st 2026

5-12 Weeks

Programming Algorithms Logic

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.

Sep 14th 2026

3 Weeks

Algorithms DSP Signal Processing

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.

Sep 18th 2026

4 Weeks

Algorithms Approximation Algorithms LP Relaxation

Coursera

University of Alberta

Problem Solving, Python Programming, and Video Games (Coursera)

CS: Programming

This course is an introduction to computer science and programming in Python. Important computer science concepts such as problem solving (computational thinking), problem decomposition, algorithms, abstraction, and software quality are emphasized throughout. The Python programming language and video games are used to demonstrate computer science concepts in a concrete and fun manner. However, a learner can take the knowledge and skills from this course and apply them to non-game problems, other programming languages, and other computer science courses.

Sep 21st 2026

5-12 Weeks

Programming Python Algorithms

Coursera

Fred Hutchinson Cancer Center

Practical Steps for Building Fair AI Algorithms (Coursera)

Computer Science

Algorithms increasingly help make high-stakes decisions in healthcare, criminal justice, hiring, and other important areas. This makes it essential that these algorithms be fair, but recent years have shown the many ways algorithms can have biases by age, gender, nationality, race, and other attributes. This course will teach you ten practical principles for designing fair algorithms. It will emphasize real-world relevance via concrete takeaways from case studies of modern algorithms, including those in criminal justice, healthcare, and large language models like ChatGPT. You will come away with an understanding of the basic rules to follow when trying to design fair algorithms, and assess algorithms for fairness.

Sep 14th 2026

4 Weeks

Algorithms Algorithm Design Bias

Coursera

University of California, Santa Cruz

C++ For C Programmers, Part B (Coursera)

CS: Software Engineering CS: Programming

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

Sep 7th 2026

5-12 Weeks

Programming Algorithms C++