Lecture 5: Trees and greedy algorithms
- Minimum spanning tree (MST) problem
definition of MST, Kruskal's greedy algorithm (with a proof), Jarník's algorithm (later known as Prim's algorithm), other relations
- Principles of greedy algorithms
local "greedy" optimization, a simple job assignment problem with a greedy solution, when greedy solutions do not work optimally
- Matroids and abstract greedy optimization
three axioms of independent sets of a matroid, matroid bases, the cycle matroid on the edges of a graph (independent = acyclic), the relation between matroids and an abstract greedy algorithm
This lecture primarily introduces the "greedy" method of discrete optimization - a step-by-step search through local optima which eventually leads (or should lead) to the global optimum. The method is illustrated with greedy algorithms for the Minimum Spanning Tree problem (MST - one of the basic discrete optimization problems), and a simple variant of a job assignment. The abstract greedy algorithm then motivates the introduction of matroids - useful (though rather obscure) discrete structures generalizing graphs.
Study the whole Sections 5.3, 5.4, and 5.5.
Furthermore, have a short look at extensive online resources about greedy algorithms and specifically the MST problem.