Greed is good.
Greed is right.
Greed cuts through,
essence of the
Simple idea, but it doesnt always work.
Used to solve optimization problems that involve choosing
objects, events, (some type of entities) from a set.
The Greedy Strategy:
At each step, make the best next choice.
Never backtrack or change past choices.
Never look ahead to see if this choice has negative
Depending on the problem: this may or may not give
the correct answer.
The text treats greedy algorithms as a special case
of dynamic programming
The greedy paradigm is simpler
We will do greedy algorithms first
1 Properties of Greedy Algorithms
Usually simple and fast (often linear time).
Hard part is demonstrating optimality.
Examples: Huffman encoding, some sorting
Typically applied to optimization problems
(find solution which maximizes or minimizes
some objective function).
Example: Making Change
Suppose we are given the specification of a
monetary denominational system
(a list of the values of different coins that are in use,
for example: 1, 5, 10, 25, 100, 200 cents).
We are also given an amount (specified in cents)
to return to a customer
Do this using the fewest number of coins
Used in AD 117-138
The Coin Changing Problem
Assume that we have an unlimited number of coins of
1c (pennies), 5c (nickels), 10c (dimes), 25c (quarters), 1$ (loonies)
Objective: Pay out a given sum S with the smallest
number of coins possible.
The greedy coin changing algorithm :
This is a (m) algorithm where m = number of denominations.
while S > 0 do
c := value of the largest coin no larger than S;
num := S div c;
pay out num coins of value c;
S := S - num*c;
3 Example: Making Change
$5.64 = $2 +$2 + $1 +
.25 + .25 + .10 +
.01 + .01 + .01 +.01
Nontrivial exercise: prove this always uses
smallest number of coins
set up a monetary system for which this
Framework for Greedy Algorithms
At each stage, we have a partial solution
which can be extended to a larger solution.
We have a set of choices for this next step and
we select a good choice to extend the solution.
We have some sort of predefined measure
of what a good choice is.
Take the best choice under that measure.
Repeat until a complete solution is obtained.