Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Stanford Online · View on Coursera ↗
Taught by Tim Roughgarden
Computer ScienceMath and Logic
About the course
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).
The dissent
The most-upvoted critical review (2 votes, 3.0★).
“From the entire specialization, this course was the most difficult for me. I am giving less stars on this one just because I believe there was a detail on the TSP Dynamic Programming solution that was seen for the first time on the entire specialization and it was not offered proper explanation for how to approach it. Namely, the part of 2-D array indexed by subsets. I really struggled with this aspect during the implementation and I had to do additional research where I found the concept of PowerSet and how to use bit manipulation to represent power sets.”
Coursera's 4.8 comes from 832 ratings. Of those, 0.7% are 1–2★.
Starisk reads the reviews learners voted most helpful, and weights each by the square root of its votes: a review with 80 upvotes counts about five times one with 2. Unvoted reviews are not skipped out of laziness — by this model they carry no evidence that other students endorsed them.
That measures what the most-endorsed reviews say, not “true quality.” The rating distribution above is the whole population, so you can see the sample next to it.
Reviews read on 23 Oct 2026.Read them on Coursera ↗