Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Offered By: Stanford University via Coursera
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
Approximation Algorithms Part IÉcole normale supérieure via Coursera Approximation Algorithms Part II
École normale supérieure via Coursera Algorithm Design and Analysis
University of Pennsylvania via edX Delivery Problem
University of California, San Diego via Coursera Approximation Algorithms
EIT Digital via Coursera