Stanford University - Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
- Offered byCoursera
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them at Coursera Overview
Duration | 14 hours |
Total fee | Free |
Mode of learning | Online |
Difficulty level | Intermediate |
Official Website | Explore Free Course  |
Credential | Certificate |
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them at Coursera Highlights
- Shareable Certificate Earn a Certificate upon completion
- 100% online Start instantly and learn at your own schedule.
- Course 4 of 4 in the Algorithms Specialization
- Flexible deadlines Reset deadlines in accordance to your schedule.
- Intermediate Level
- Approx. 14 hours to complete
- English Subtitles: Arabic, French, Portuguese (European), Italian, Vietnamese, German, Russian, English, Spanish
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them at Coursera Course details
- 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).
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them at Coursera Curriculum
Week 1
Single-Source Shortest Paths, Revisted
Optimal Substructure
The Basic Algorithm I
The Basic Algorithm II
Detecting Negative Cycles
A Space Optimization
Internet Routing I [Optional]
Internet Routing II [Optional]
Problem Definition
Optimal Substructure
The Floyd-Warshall Algorithm
A Reweighting Technique
Johnson's Algorithm I
Johnson's Algorithm II
Week 1 Overview
Overview, Resources, and Policies
Lecture Slides
Optional Theory Problems (Week 1)
Problem Set #1
Programming Assignment #1
Week 2
Polynomial-Time Solvable Problems
Reductions and Completeness
Definition and Interpretation of NP-Completeness I
Definition and Interpretation of NP-Completeness II
The P vs. NP Question
Algorithmic Approaches to NP-Complete Problems
The Vertex Cover Problem
Smarter Search for Vertex Cover I
Smarter Search for Vertex Cover II
The Traveling Salesman Problem
A Dynamic Programming Algorithm for TSP
Week 2 Overview
Optional Theory Problems (Week 2)
Problem Set #2
Programming Assignment #2
Week 3
A Greedy Knapsack Heuristic
Analysis of a Greedy Knapsack Heuristic I
Analysis of a Greedy Knapsack Heuristic II
A Dynamic Programming Heuristic for Knapsack
Knapsack via Dynamic Programming, Revisited
Ananysis of Dynamic Programming Heuristic
Week 3 Overview
Problem Set #3
Programming Assignment #3
Week 4
The Maximum Cut Problem I
The Maximum Cut Problem II
Principles of Local Search I
Principles of Local Search II
The 2-SAT Problem
Random Walks on a Line
Analysis of Papadimitriou's Algorithm
Stable Matching [Optional]
Matchings, Flows, and Braess's Paradox [Optional]
Linear Programming and Beyond [Optional]
Epilogue
Week 4 Overview
Optional Theory Problems (Week 4)
Info and FAQ for final exam
Problem Set #4
Programming Assignment #4
Final Exam
Other courses offered by Coursera
Student Forum
Anything you would want to ask experts?
TechnologyComputer ScienceData Structures and AlgorithmsShortest Paths Revisited, NP-Complete Problems and What To Do About Them