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

40 views25 pages
user avatar
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 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
Unlock document

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

Already have an account? Log in
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)
to return to a customer
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.

Already have an account? Log in
3
Alexandrian
Coin
Denominations
Used in AD 117-138
Time of emperor
Hadrian
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.

Already have an account? Log in

Document Summary

Greed cuts through, clarifies, and captures the essence of the evolutionary spirit. 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 look ahead to see if this choice has negative consequences: 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. 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). 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).