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

40 views25 pages

Published on 16 Oct 2011

Department

Computer Science

Course

CS341

Professor

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

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

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;

## 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).