main page — CS 566 Efficient Algorithms
Unit 11: Greedy Algorithms
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
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)