Algorithm Design: Greedy Algorithms

Greedy algorithms

Many algorithms are iterative procedures that choose among a number of alternatives at each iteration. For example, a cashier can view the Change Problem as a series of decisions they have to make: which coin (among $d$ denominations) to return first, which to return second, and so on. Some of these alternatives might lead to correct solutions, while others might not.

Change example

Greedy algorithms choose the most attractive alternative at each iteration—for example, the ...