This course is part of the Algorithms Specialization

4.8
stars
786 ratings

Tim Roughgarden

40,246 already enrolled

Offered By

Algorithms SpecializationStanford University

About this Course

13,545 recent views

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

Flexible deadlines

Reset deadlines in accordance to your schedule.

Shareable Certificate

Earn a Certificate upon completion

100% online

Start instantly and learn at your own schedule.

Coursera Labs

Includes hands on learning projects.

Learn more about Coursera Labs

Course 4 of 4 in the

Algorithms Specialization

Intermediate Level

Approx. 13 hours to complete

English

Skills you will gain

Data Structure
Algorithms
Np-Completeness
Dynamic Programming

Flexible deadlines

Reset deadlines in accordance to your schedule.

Shareable Certificate

Earn a Certificate upon completion

100% online

Start instantly and learn at your own schedule.

Coursera Labs

Includes hands on learning projects.

Learn more about Coursera Labs

Course 4 of 4 in the

Algorithms Specialization

Intermediate Level

Approx. 13 hours to complete

English

Instructor

Instructor rating

4.87/5 (54 Ratings)

Tim Roughgarden

Offered by

Stanford University

Syllabus - What you will learn from this course

Content Rating95%(1,360 ratings)

Week1

Week 1

4 hours to complete

Week 1

4 hours to complete

14 videos (Total 151 min), 4 readings, 2 quizzes

14 videos

Single-Source Shortest Paths, Revisted10mOptimal Substructure10mThe Basic Algorithm I8mThe Basic Algorithm II10mDetecting Negative Cycles9mA Space Optimization12mInternet Routing I [Optional]11mInternet Routing II [Optional]6mProblem Definition7mOptimal Substructure12mThe Floyd-Warshall Algorithm13mA Reweighting Technique14mJohnson's Algorithm I11mJohnson's Algorithm II11m

4 readings

Week 1 Overview10mOverview, Resources, and Policies10mLecture Slides10mOptional Theory Problems (Week 1)10m

2 practice exercises

Problem Set #130mProgramming Assignment #130m

Week2

Week 2

3 hours to complete

Week 2

3 hours to complete

11 videos (Total 122 min), 2 readings, 2 quizzes

11 videos

Polynomial-Time Solvable Problems14mReductions and Completeness13mDefinition and Interpretation of NP-Completeness I10mDefinition and Interpretation of NP-Completeness II7mThe P vs. NP Question9mAlgorithmic Approaches to NP-Complete Problems12mThe Vertex Cover Problem8mSmarter Search for Vertex Cover I9mSmarter Search for Vertex Cover II7mThe Traveling Salesman Problem14mA Dynamic Programming Algorithm for TSP12m

2 readings

Week 2 Overview10mOptional Theory Problems (Week 2)10m

2 practice exercises

Problem Set #230mProgramming Assignment #230m

Week3

Week 3

2 hours to complete

Week 3

2 hours to complete

6 videos (Total 68 min), 1 reading, 2 quizzes

Week4

Week 4

4 hours to complete

Week 4

4 hours to complete

11 videos (Total 124 min), 3 readings, 3 quizzes

11 videos

The Maximum Cut Problem I8mThe Maximum Cut Problem II9mPrinciples of Local Search I8mPrinciples of Local Search II10mThe 2-SAT Problem14mRandom Walks on a Line16mAnalysis of Papadimitriou's Algorithm14mStable Matching [Optional]15mMatchings, Flows, and Braess's Paradox [Optional]13mLinear Programming and Beyond [Optional]11mEpilogue1m

3 readings

Week 4 Overview10mOptional Theory Problems (Week 4)10mInfo and FAQ for final exam10m

3 practice exercises

Problem Set #430mProgramming Assignment #430mFinal Exam30m

Reviews

4.8

107 reviews

5 stars
85.38%
4 stars
12.83%
3 stars
1.14%
2 stars
0.50%
1 star
0.12%

TOP REVIEWS FROM SHORTEST PATHS REVISITED, NP-COMPLETE PROBLEMS AND WHAT TO DO ABOUT THEM

by ASAug 22, 2018

This is the most challenging course in this specialization. Assignments as well as test questions require good amount of thinking.

One of the best courses I did on Coursera.

by LCMay 1, 2018

Fantastic course by a fantastic Teacher, Prof. Roughgarden manages to turn the dry subject of Algorithms into a hot sexy one!!

by PRJun 24, 2018

Great one for people with advanced understanding! Others will find it slightly hard to follow!

by SWAug 9, 2020

Excellent course! The lectures provide clear and rigorous explanations, and the coding exercises are appropriately challenging.

View all reviews

About the Algorithms Specialization

Algorithms are the heart of computer science, and the subject has countless practical applications as well as intellectual depth. This specialization is an introduction to algorithms for learners with at least a little programming experience. The specialization is rigorous but emphasizes the big picture and conceptual understanding over low-level implementation and mathematical details. After completing this specialization, you will be well-positioned to ace your technical interviews and speak fluently about algorithms with other programmers and computer scientists.

Frequently Asked Questions

When will I have access to the lectures and assignments?
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
What will I get if I subscribe to this Specialization?
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.
Is financial aid available?
Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.

More questions? Visit the Learner Help Center.

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

About this Course

Skills you will gain