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 California, San Diego

Finding Hidden Messages in DNA (Bioinformatics I) (Coursera)

Sci: Biology & Life Sciences Health & Society

This course begins a series of classes illustrating the power of computing in modern biology. Please join us on the frontier of bioinformatics to look for hidden messages in DNA without ever needing to put on a lab coat. In the first half of the course, we investigate DNA replication, and ask the question, where in the genome does DNA replication begin? We will see that we can answer this question for many bacteria using only some straightforward algorithms to look for hidden messages in the genome.

Oct 26th 2026

5-12 Weeks

Biology Algorithms DNA

Coursera

The University of Tokyo

Interactive Computer Graphics (Coursera)

CS: Software Engineering

Computer graphics can be a powerful tool for supporting visual problem solving, and interactivity plays a central role in harnessing the users' creativity. This course will introduce various interactive tools developed in computer graphics research field with their design rationales and algorithms.

Nov 2nd 2026

5-12 Weeks

Robotics Algorithms Computer Graphics

Coursera

Princeton University

Analytic Combinatorics (Coursera)

CS: Theory Sci: Mathematics

Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations. All the features of this course are available for free. It does not offer a certificate upon completion.

Nov 2nd 2026

5-12 Weeks

Math Calculus Analytic Combinatorics

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

Coursera

Princeton University

Analysis of Algorithms (Coursera)

CS: Theory

This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.

Oct 26th 2026

5-12 Weeks

Math Calculus Analysis

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.

Nov 9th 2026

4 Weeks

IPython Data Analysis Computer Programming

Coursera

Princeton University

Algorithms, Part II (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 9th 2026

5-12 Weeks

Java Algorithms Data Structures

Coursera

University of Michigan

Estructuras de datos de Python (Coursera)

CS: Software Engineering Computer Science

Este curso presentará las estructuras de datos básicas del lenguaje de programación Python. Veremos los conceptos básicos de la programación de procedimientos y exploraremos cómo podemos usar las estructuras de datos integrados de Python, como listas, diccionarios y tuplas, para realizar análisis de datos cada vez más complejos. Este curso abarcará los capítulos 6 a 10 del libro de texto “Python para todos”. Este curso cubre Python 3.

Nov 9th 2026

5-12 Weeks

Python Data Structures Dictionary

Coursera

University of Michigan

Problem Solving Using Computational Thinking (Coursera)

CS: Theory Computer Science

Have you ever heard that computers "think"? Believe it or not, computers really do not think. Instead, they do exactly what we tell them to do. Programming is, "telling the computer what to do and how to do it." Before you can think about programming a computer, you need to work out exactly what it is you want to tell the computer to do. Thinking through problems this way is Computational Thinking. Computational Thinking allows us to take complex problems, understand what the problem is, and develop solutions. We can present these solutions in a way that both computers and people can understand.

Nov 9th 2026

5-12 Weeks

Programming Algorithms Computational Thinking

Coursera

University of Michigan

Estruturas de dados Python (Coursera)

CS: Software Engineering CS: Programming

Este curso apresentará as estruturas de dados centrais da linguagem de programação Python. Vamos superar os fundamentos da programação de procedimentos e explorar como podemos usar as estruturas de dados integradas do Python, como listas, dicionários e tuplas, para realizar análises de dados cada vez mais complexas. Este curso cobrirá os capítulos 6 a 10 do livro “Python para Todos”. Este curso aborda o Python 3.

Nov 2nd 2026

5-12 Weeks

Programming Python Semantics

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

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