# CS341 Lecture Notes - Greedy Algorithm, Gordon Gekko, Huffman Coding

40 views25 pages
Published on 16 Oct 2011
School
University of Waterloo
Department
Computer Science
Course
CS341
1
Greedy Algorithms
“Greed is good.
Greed is right.
Greed works.
Greed cuts through,
clarifies, and
captures the
essence of the
evolutionary spirit.”
-Gordon Gekko
(Michael Douglas) http://en.wikipedia.org/wiki/Wall_Street_(film)
Greedy Algorithms
Simple idea, but it doesn’t 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
consequences.
Depending on the problem: this may or may not give
The text treats greedy algorithms as a special case
of dynamic programming
We will do greedy algorithms first
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 25 pages and 3 million more documents.

2
Properties of Greedy Algorithms
Usually simple and fast (often linear time).
Hard part is demonstrating optimality.
Examples: Huffman encoding, some sorting
algorithms.
Typically applied to optimization problems
(find solution which maximizes or minimizes
some objective function).
Example: Making Change
Input:
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)
Problem:
Do this using the fewest number of coins
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 25 pages and 3 million more documents.

3
Alexandrian
Coin
Denominations
Time of emperor
The Coin Changing Problem
Assume that we have an unlimited number of coins of
various denominations:
1c (pennies), 5c (nickels), 10c (dimes), 25c (quarters), 1\$ (loonies)
Objective: Pay out a given sum Swith 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;
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 25 pages and 3 million more documents.