Chapter 15: Greedy Algorithms: Activity Selection, Huffman Codes, and Caching

The activity selection problem serves as the primary example, where the goal is to schedule the maximum number of non-overlapping activities by always selecting the one with the earliest finish time — an approach provable by induction and exchange arguments that runs in Θ(n) time after O(n log n) sorting. The chapter sharpens the distinction between greedy algorithms and dynamic programming through the knapsack problem: the fractional variant, where items can be divided, yields to a greedy strategy of selecting by highest value per pound, while the 0-1 variant, where items must be taken whole, requires dynamic programming because early greedy choices can foreclose globally optimal combinations. Huffman coding demonstrates a particularly powerful greedy application, building an optimal prefix-free binary code for data compression by repeatedly merging the two lowest-frequency characters using a min-priority queue, assigning shorter codes to more frequent characters and achieving a total cost B(T) equal to the sum of each character's frequency times its codeword length — all in O(n log n) time and proven optimal via greedy-choice and optimal-substructure lemmas. The chapter closes with the offline caching problem, where the furthest-in-future strategy — evicting whichever cached block is needed least soon — is proven optimal and serves as a theoretical benchmark against which practical online strategies like LRU, which must operate without knowledge of future requests, are measured.