Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 16

In this chapter, the authors look at greedy algorithms. A greedy algorithm makes a locally optimal choice in a hope that it will lead to a globally optimal solution. Greedy algorithms do not always give optimal solutions.

The authors then discuss activity selection problem where there is a set $ S = \{a_1, a_2, ..., a_n\} $ of $ n $ activities. Each activity $ a_i $ has a start time $ s_i $ and finish time $ f_i $ where $ 0 <= s_i < f_i < \infty $. If selected, activity $ a_i $ takes place during half open time interval $ [s_i,f_i) $. Activities $ a_i $ and $ a_j $ are compatible if the intervals $[s_i,f_i)$ and $[s_j,f_j)$ do not overlap. The activity selection problem is to select maximum sized subset of mutually compatible activities.

The authors then formulate a dynamic programming solution for the problem. The authors prove that inclusion of the activity that has the earliest finish time leaves the largest amount of unscheduled time and thus will be part of the optimal solution to the activity-selection problem. The authors then provide recursive as well as iterative greedy algorithms and prove that the running time of the algorithms are $ \Theta (n) $.

The authors then provide two different set of steps to find a greedy solution to a problem, one that follows dynamic programming steps of finding the optimal sub-structure and the other that depends on greedy choice of local optimal solution.

The authors then discuss 0-1 knapsack problem and fractional knapsack problem to show the difference between greedy method and dynamic programming method. An optimal solution to the former problem requires dynamic programming while the later only needs greedy method.

The authors then discuss Huffman Codes, which uses variable length bit-encoding to compress data. The authors discuss about prefix code where no codeword is a prefix of another codeword. The authors then provide Huffman's greedy method to generate the prefix code given the frequencies of characters.

The authors then discuss combinatorial structures called matroids which are used to define the theory of greedy methods. The authors discuss about matric matroid and graphic matroid. They then prove that matroids exhibit both optimal substructure property and greedy-choice property.

The authors discuss task-scheduling problem and provide $ O(n^2) $ time greedy algorithm to solve it.