Stanford University - Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
- Offered byCoursera
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming at Coursera Overview
Duration | 15 hours |
Total fee | Free |
Mode of learning | Online |
Difficulty level | Intermediate |
Official Website | Explore Free Course  |
Credential | Certificate |
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming at Coursera Highlights
- Shareable Certificate Earn a Certificate upon completion
- 100% online Start instantly and learn at your own schedule.
- Course 3 of 4 in the Algorithms Specialization
- Flexible deadlines Reset deadlines in accordance to your schedule.
- Intermediate Level
- Approx. 15 hours to complete
- English Subtitles: Arabic, French, Portuguese (European), Italian, Vietnamese, German, Russian, English, Spanish
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming at Coursera Course details
- 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).
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming at Coursera Curriculum
Week 1
Application: Internet Routing
Application: Sequence Alignment
Introduction to Greedy Algorithms
Application: Optimal Caching
Problem Definition
A Greedy Algorithm
Correctness Proof - Part I
Correctness Proof - Part II
Handling Ties [Advanced - Optional]
MST Problem Definition
Prim's MST Algorithm
Correctness Proof I
Correctness Proof II
Proof of Cut Property [Advanced - Optional]
Fast Implementation I
Fast Implementation II
Week 1 Overview
Overview, Resources, and Policies
Lecture slides
Optional Theory Problems (Week 1)
Problem Set #1
Programming Assignment #1
Week 2
Kruskal's MST Algorithm
Correctness of Kruskal's Algorithm
Implementing Kruskal's Algorithm via Union-Find I
Implementing Kruskal's Algorithm via Union-Find II
MSTs: State-of-the-Art and Open Questions [Advanced - Optional]
Application to Clustering
Correctness of Clustering Algorithm
Lazy Unions [Advanced - Optional]
Union-by-Rank [Advanced - Optional]
Analysis of Union-by-Rank [Advanced - Optional]
Path Compression [Advanced - Optional]
Path Compression: The Hopcroft-Ullman Analysis I [Advanced - Optional]
Path Compression: The Hopcroft-Ullman Analysis II [Advanced - Optional]
The Ackermann Function [Advanced - Optional]
Path Compression: Tarjan's Analysis I [Advanced - Optional]
Path Compression: Tarjan's Analysis II [Advanced - Optional]
Week 2 Overview
Optional Theory Problems (Week 2)
Problem Set #2
Programming Assignment #2
Week 3
Introduction and Motivation
Problem Definition
A Greedy Algorithm
A More Complex Example
Correctness Proof I
Correctness Proof II
Introduction: Weighted Independent Sets in Path Graphs
WIS in Path Graphs: Optimal Substructure
WIS in Path Graphs: A Linear-Time Algorithm
WIS in Path Graphs: A Reconstruction Algorithm
Principles of Dynamic Programming
Week 3 Overview
Problem Set #3
Programming Assignment #3
Week 4
The Knapsack Problem
A Dynamic Programming Algorithm
Example [Review - Optional]
Optimal Substructure
A Dynamic Programming Algorithm
Problem Definition
Optimal Substructure
Proof of Optimal Substructure
A Dynamic Programming Algorithm I
A Dynamic Programming Algorithm II
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 AlgorithmsGreedy Algorithms, Minimum Spanning Trees, and Dynamic Programming