main page — CS 566 Efficient Algorithms
Unit 11: Greedy Algorithms
This is an archived version of this module from Winter 2024-25.
This unit covers the greedy paradigm and discusses examples of greedy algorithms for exemplary algorithmic problems:
- Making-change problem
- Huffman coding (recap)
- Kruskal’s MST algorithm
- Prim’s MST algorithm
- Dijkstra’s shortest path algorithm
- Activity selection
It also briefly covers the concept of matroids.
Learning outcomes
- Describe informally what greedy algorithms are.
- Know exemplary problems and their greedy solutions: Change-Making Problem, MSTs, SSSPP, Assignment Problem.
- Be able to design and proof correctness of greedy algorithms for (simple) algorithmic problems.
- Be able to explain the matroid properties and its relation to greedy algorithms.
Material
- slides
- Video 11-1 (2025-01-14):
§11.1 Greedy Introduction
- Video 11-2 (2025-01-14):
§11.2 The Making-changing problem
- Video 11-3 (2025-01-14):
§11.3 Minimum Spanning Trees: Kruskal’s Algorithm
- Video 11-4 (2025-01-20):
§11.4 Minimum Spanning Trees: Prim’s Algorithm
- Video 11-5 (2025-01-20):
§11.5 Shortest Path: Dijkstra’s Algorithm
- Video 11-6 (2025-01-21):
§11.6 Greedy Scheduling: Activity Selection
- Video 11-7 (2025-01-21):
§11.7 Matroids
Further reading and sources
The presentation of the making-change problem is my own. Further reading on greedy coin denominations can be found in
The MST presentation follows
- Nebel, Wild: Entwurf und Analyse von Algorithmen (2018), Springer Vieweg
- Sedgewick, Wayne: Algorithms 4th ed (2011), Pearson
The state of the art MST algorithms are described in the following research papers:
- Chazelle: A minimum spanning tree algorithm with inverse-Ackermann type complexity (2000)
- Fredman, Willard: Trans-dichotomous algorithms for minimum spanning trees and shortest paths (1994)
- Karger, Klein, Tarjan: A randomized linear-time algorithm to find minimum spanning trees (1995)