Class Notes (839,462)
Canada (511,348)
CS 341 (26)

Lecture #6 - Greedy Algorithms Fall 2009

25 Pages

Computer Science
Course Code
CS 341
Forbes Burkowski

This preview shows pages 1,2,3,4. Sign up to view the full 25 pages of the document.
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) Greedy Algorithms 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 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 1 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 2 Alexandrian Coin Denominations Used in AD 117-138 Timeof 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 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 E.g.: $5.64 = $2 +$2 + $1 + .25 + .25 + .10 + .01 + .01 + .01 +.01 Nontrivial exercise: prove this always uses smallest number of coins Easier exercise: set up a monetary system for which this algorithm fails 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. 4
More Less
Unlock Document

Only pages 1,2,3,4 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.