Greedy Algorithms — Activity Selection, Huffman Codes, Knapsack, and Caching Explained | Chapter 15 of Intro to Algorithms

Greedy algorithms provide fast and elegant solutions to many optimization problems by making the best local decision at each step, hoping this strategy leads to an optimal global solution. Chapter 15 of introduction to algorithms dives into the greedy approach, contrasting it with dynamic programming, and walks through key applications: activity selection, fractional and 0-1 knapsack, Huffman coding for data compression, and caching strategies. Understanding when the greedy-choice property holds is essential to recognizing which problems are truly “greedy-amenable.”

For a quick video breakdown and worked examples, watch the full chapter summary below. Don’t forget to subscribe to Last Minute Lecture for new algorithm tutorials.

The Greedy Strategy

A greedy algorithm chooses the best available option at each stage, never reconsidering earlier decisions. This simplicity often leads to efficient algorithms, provided the greedy-choice property and optimal substructure are present. Unlike dynamic programming, which may revisit and combine solutions to subproblems, greedy algorithms stick with choices made and move forward.

Activity Selection Problem

This classic problem asks: given a set of activities with start and finish times, how can we schedule the most non-overlapping activities? The greedy solution always picks the activity that finishes earliest, then recursively selects the next compatible one. This approach, when paired with a pre-sorted list (by finish time), solves the problem in O(n) time after sorting. Its optimality is proven via induction and exchange arguments.

Greedy vs. Dynamic Programming: Knapsack Problems

While both paradigms exploit optimal substructure, only problems with the greedy-choice property are truly “greedy.” For the fractional knapsack problem (where you can take fractions of items), the greedy approach of picking by value-to-weight ratio yields the optimal solution. However, in the 0-1 knapsack problem (items must be fully included or excluded), greedy fails and dynamic programming is required for an optimal answer.

Huffman Coding for Data Compression

Huffman coding constructs an optimal, prefix-free binary code based on character frequencies, assigning shorter codes to more frequent characters. Using a min-priority queue, the algorithm repeatedly merges the two lowest-frequency nodes, building a binary tree whose leaves represent characters. Huffman codes minimize the weighted average codeword length and run in O(n log n) time. This approach is widely used in lossless data compression formats.

Offline Caching: Furthest-in-Future and LRU

In the offline caching problem (where the entire sequence of requests is known ahead of time), the optimal eviction strategy is to remove the item whose next use is furthest in the future. This furthest-in-future strategy serves as a gold standard for online algorithms, such as Least Recently Used (LRU), which operates without future knowledge. Understanding these concepts is critical for systems design, memory management, and web caching.

Glossary of Key Terms

• Greedy Algorithm: Makes the best local choice at every step
• Optimal Substructure: Optimal solution is composed of optimal subproblem solutions
• Greedy-Choice Property: Greedy decisions yield a global optimum
• Fractional Knapsack: Items can be split; solved greedily
• 0-1 Knapsack: Items are all-or-nothing; requires DP
• Prefix-Free Code: No codeword is a prefix of another
• Huffman Code: Greedy algorithm for optimal prefix coding
• Min-Priority Queue: Data structure for extracting minimum-frequency elements
• Offline Caching: Cache management with full request sequence known
• Cache Miss: Requested item not in cache
• Eviction Strategy: Rule for removing items from a full cache
• Furthest-in-Future: Optimal offline cache eviction
• LRU: Least Recently Used online cache eviction

Conclusion: When to Be Greedy?

Greedy algorithms are among the most elegant tools in an algorithm designer’s toolkit, but their applicability depends on the specific structure of a problem. Chapter 15 of introduction to algorithms demonstrates where and why the greedy strategy works, especially for activity selection and Huffman coding, and where more robust approaches like dynamic programming are required. Mastering this distinction enables the creation of efficient, correct algorithms in both theory and practice.

Ready for more algorithm deep-dives? Subscribe to Last Minute Lecture and check out the full series of introduction to algorithms chapter summaries.