Chapter 10: Greedy algorithms

Introduction

The chapter introduction previews greedy strategies, NP-hard problems, and approximation algorithms.

10.1 The classroom scheduling problem

The section solves the classroom scheduling problem by repeatedly choosing the compatible class that ends soonest, then uses that example to explain greedy algorithms.

• Earliest-Finishing Class Selection: Describe how to choose a maximum-size set of nonoverlapping classes by first taking the class that ends soonest, then repeatedly taking the earliest-ending class that starts after the previous one ends.
  Why it matters: The eligibility check and earliest-finish rule together explain how this simple choice produces the schedule.
• Greedy Choices and Optimality: Explain that a greedy algorithm picks a locally optimal move at each step, and that this yields a globally optimal answer for this scheduling problem, though greedy algorithms do not always work.
  Why it matters: This example shows both the appeal of a greedy choice and the limit of assuming it works everywhere.

Key terms: classroom scheduling problem, ends the soonest, greedy algorithm, locally optimal solution, globally optimal solution

10.2 The knapsack problem

This section uses a knapsack example to show that a simple greedy choice can miss the most valuable combination, while still being useful when a good-enough answer will do.

• Greedy knapsack choice and limit: Describe the greedy knapsack strategy and explain, using the stereo, laptop, and guitar example, why it does not always maximize total value.
  Why it matters: A choice that looks best right now may prevent a better overall result.
• Value of good enough results: Explain why a greedy algorithm can still be useful when it does not guarantee the optimal solution.
  Why it matters: Not every problem requires a perfect answer if a simple approach gives a useful one.

Key terms: greedy strategy, knapsack, optimal solution, greedy algorithms, good enough

10.3 The set-covering problem

The section defines the set-covering problem through a radio-station example and shows why finding the smallest exact solution becomes difficult as the number of stations grows.

• Minimum station coverage: Describe the radio-station problem: choose as few stations as possible while reaching all 50 states, even though stations’ coverage overlaps.
  Why it matters: This is the problem the later approximation method tries to address.
• Exhaustive search cost: Explain how to find the exact smallest selection by listing every subset of stations and choosing the smallest one that covers all states, and why this becomes impractical as stations are added.
  Why it matters: The rapidly growing number of subsets explains why a different approach is needed for many stations.

Key terms: set-covering problem, stations, states, power set, subset, O(2n)

10.4 Approximation algorithms

The section gives a greedy approximation for covering all states with radio stations and explains how to judge it against an exact solution.

• Greedy station selection: Describe the greedy rule for choosing radio stations and when to stop.
  Why it matters: This rule is the section’s practical way to build a covering set of stations.
• Approximation algorithm tradeoff: Explain why this greedy approach is an approximation algorithm and how approximation algorithms are judged.
  Why it matters: A quick answer is useful when finding the exact best answer takes too long, but its quality still matters.

Key terms: greedy algorithm, states, station, approximation algorithm, optimal solution, O(n2)

10.5 Code for setup

The section sets up the data structures for a station-selection example and explains why sets are useful for representing states.

• Station Selection Data Setup: Describe how the example represents the states to cover, the available stations, and the stations ultimately chosen.
  Why it matters: These structures identify what needs covering, what each station covers, and where the choices go.
• Set Uniqueness: Explain how a set differs from a list in the example.
  Why it matters: Uniqueness explains the choice to represent collections of states as sets.

Key terms: set, dict, states, stations, list, duplicates

10.6 Calculating the answer

This section explains how to choose the station that covers the most states not yet covered.

• Best station selection: Explain how to choose best_station by checking every station for the most newly covered states, and describe what states_covered tracks.
  Why it matters: Counting only newly covered states is what makes the station comparison useful.

Key terms: best_station, states_covered, uncovered states, for loop

10.7 Sets

This section introduces sets as duplicate-free collections and explains union, intersection, and difference.

• Set operations: Explain what union, intersection, and difference do to two sets, using the fruit and vegetable sets as an example.
  Why it matters: These operations give you ways to combine and compare collections of items.
• Duplicate-free sets: Distinguish a set from a list in the way this section describes.
  Why it matters: Remembering that sets exclude duplicates helps you describe what kind of collection these operations act on.

Key terms: set union, set intersection, set difference, sets, lists, duplicates

10.8 Back to the code

Explains how the greedy set-covering loop chooses stations and updates uncovered states, then notes its speed-versus-exactness tradeoff.

• Greedy station selection loop: Trace how the loop chooses a station, adds it to the result, and updates the states still needing coverage.
  Why it matters: This is how the code turns a local choice into a collection of stations that covers all needed states.
• Speed and exactness tradeoff: Explain why the greedy set-covering result need not be an exact answer despite the algorithm running much faster than the exact algorithm.
  Why it matters: It clarifies why a fast greedy result should not automatically be treated as an exact solution.

Key terms: covered, states_needed, states_for_station, best_station, final_stations, greedy algorithm, exact answer, set-covering problem, NP-hard

10.9 Recap

This recap connects greedy algorithms’ local choices with their usefulness as fast, easy-to-write approximation algorithms for NP-hard problems.

• Local Versus Global Optimization: Explain that greedy algorithms optimize locally in the hope of reaching a global optimum.
  Why it matters: This distinction captures both the greedy approach and its limitation.
• Greedy Approximation for NP-Hard Problems: Explain why the recap recommends approximation algorithms for NP-hard problems and identifies greedy algorithms as good candidates.
  Why it matters: It explains when the book recommends considering a greedy approach and why.

Key terms: greedy algorithms, locally, global optimum, NP-hard problem, approximation algorithm