This course is part of the Algorithms Specialization

4.8
stars
1,217 ratings

Tim Roughgarden

68,725 already enrolled

Offered By

Algorithms SpecializationStanford University

About this Course

24,893 recent views

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

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 3 of 4 in the

Algorithms Specialization

Intermediate Level

Approx. 15 hours to complete

English

Skills you will gain

Spanning Tree
Algorithms
Dynamic Programming
Greedy Algorithm

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 3 of 4 in the

Algorithms Specialization

Intermediate Level

Approx. 15 hours to complete

English

Instructor

Instructor rating

4.84/5 (66 Ratings)

Tim Roughgarden

Offered by

Stanford University

Syllabus - What you will learn from this course

Content Rating95%(2,482 ratings)

Week1

Week 1

4 hours to complete

Week 1

4 hours to complete

16 videos (Total 160 min), 4 readings, 2 quizzes

16 videos

Application: Internet Routing10mApplication: Sequence Alignment8mIntroduction to Greedy Algorithms12mApplication: Optimal Caching10mProblem Definition5mA Greedy Algorithm12mCorrectness Proof - Part I6mCorrectness Proof - Part II4mHandling Ties [Advanced - Optional]7mMST Problem Definition11mPrim's MST Algorithm7mCorrectness Proof I15mCorrectness Proof II8mProof of Cut Property [Advanced - Optional]11mFast Implementation I14mFast Implementation II9m

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

4 hours to complete

Week 2

4 hours to complete

16 videos (Total 188 min), 2 readings, 2 quizzes

16 videos

Kruskal's MST Algorithm7mCorrectness of Kruskal's Algorithm9mImplementing Kruskal's Algorithm via Union-Find I9mImplementing Kruskal's Algorithm via Union-Find II13mMSTs: State-of-the-Art and Open Questions [Advanced - Optional]9mApplication to Clustering11mCorrectness of Clustering Algorithm9mLazy Unions [Advanced - Optional]10mUnion-by-Rank [Advanced - Optional]12mAnalysis of Union-by-Rank [Advanced - Optional]14mPath Compression [Advanced - Optional]14mPath Compression: The Hopcroft-Ullman Analysis I [Advanced - Optional]9mPath Compression: The Hopcroft-Ullman Analysis II [Advanced - Optional]11mThe Ackermann Function [Advanced - Optional]16mPath Compression: Tarjan's Analysis I [Advanced - Optional]14mPath Compression: Tarjan's Analysis II [Advanced - Optional]13m

2 readings

Week 2 Overview10mOptional Theory Problems (Week 2)10m

2 practice exercises

Problem Set #230mProgramming Assignment #230m

Week3

Week 3

3 hours to complete

Week 3

3 hours to complete

11 videos (Total 105 min), 1 reading, 2 quizzes

11 videos

Introduction and Motivation9mProblem Definition10mA Greedy Algorithm16mA More Complex Example4mCorrectness Proof I10mCorrectness Proof II12mIntroduction: Weighted Independent Sets in Path Graphs7mWIS in Path Graphs: Optimal Substructure9mWIS in Path Graphs: A Linear-Time Algorithm9mWIS in Path Graphs: A Reconstruction Algorithm6mPrinciples of Dynamic Programming7m

1 reading

Week 3 Overview10m

2 practice exercises

Problem Set #330mProgramming Assignment #330m

Week4

Week 4

4 hours to complete

Week 4

4 hours to complete

10 videos (Total 107 min), 3 readings, 3 quizzes

10 videos

The Knapsack Problem9mA Dynamic Programming Algorithm9mExample [Review - Optional]12mOptimal Substructure13mA Dynamic Programming Algorithm12mProblem Definition12mOptimal Substructure9mProof of Optimal Substructure6mA Dynamic Programming Algorithm I9mA Dynamic Programming Algorithm II9m

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

146 reviews

5 stars
86.44%
4 stars
11.50%
3 stars
1.64%
2 stars
0.16%
1 star
0.24%

TOP REVIEWS FROM GREEDY ALGORITHMS, MINIMUM SPANNING TREES, AND DYNAMIC PROGRAMMING

by JPOct 19, 2018

Great learning experience!!!

I love dynamic p the most.

Assignment 4 is so challenging that it takes me a week to finish the program and debug it!!!

by JFJan 13, 2018

I love Tim's excitement for algorithms. He really stands out as a quality teacher in his selection of content, explanations and enthusiasm.

by SWFeb 24, 2019

One of the best courses to make a student learn DP in a way that enables him/her to think of the subproblems and way to proceed to solving these subproblems. Definitely helpful for me. Thanks.

by YWFeb 3, 2021

This course has wonderful lectures coupled with challenging but rewarding homework problems. It was a wonderful learning experience.

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.

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

About this Course

Skills you will gain