YoVDO

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

Offered By: Stanford University via Coursera

Tags

Algorithms and Data Structures Courses Bellman-Ford Algorithm Courses Algorithm Design Courses Algorithms Courses Algorithm Analysis Courses NP-completeness Courses Approximation Algorithms Courses

Course Description

Overview

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).

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.

Taught by

Tim Roughgarden

Tags

Related Courses

Advanced Algorithms and Complexity
University of California, San Diego via Coursera Advanced Data Structures in Java
University of California, San Diego via Coursera Conception et mise en œuvre d'algorithmes.
École Polytechnique via Coursera Practical Steps for Building Fair AI Algorithms
Fred Hutchinson Cancer Center via Coursera 算法设计与分析 Design and Analysis of Algorithms
Peking University via Coursera