week topic and we are at the half the course. So, let’s see the greedy algorithms today. Agenda Greedy Algorithms ● The Basics Week 4 a. Suboptimal solution Presentation ● b. Difference between Brute Force and Greedy Computer Algorithms: a. Minimal Number of Coins Examples ● First Example - Egyptian Fractions a. The Problem b. The Greedy Solution ● Second Example - Knapsack Problem a. The Problem b. The Greedy Solution The Basics Do what you can now, and what you must later
Basics of ● Sophisticated approaches as Dynamic
Programming can be overkill, specially for Greedy optimization problems
Algorithms ● Greedy algorithms is a simpler approach that
tries to solve the current stage of the problem with local information, and the solution of the next stage with need to solve it based on local information again ● Greedy algorithms do not yield optimal solutions for all problems ○ suboptimal solution, that may be enough or the best giving time/space constraints, or even the best known strategy yet The Basics Find the greatest sum
Basics of ● You try to get the maximum at each choice
Greedy Algorithms
● From the first you choose 36
● From the second you choose 40 ● From the third you choose 48 ● From the fourth you choose 50 ● It adds up 199, which is the best you can do The Basics Find the greatest sum
Basics of ● You try to get the maximum at each choice
Greedy Algorithms
● From the first you choose 12
● From the second you choose 6 ● From the third you choose 9 ● It adds up 34, which is worse than 110 The Basics From a theoretical point of view
Greedy ● Brute Force is a simple approach that usually
encompass the whole problem, while Greedy tackles Algorithms only a portion of the problem at a time
vs. Brute ● Brute Force necessarily delivers the optimal solution,
since it analyzes all possible solutions, while Greedy Force may not deliver optimal solution
Algorithms ● Brute Force algorithms usually have the worst
(sometimes the only) possible complexity, while Greedy usually have a reasonably good complexity ● Brute Force simplifies the solution by simplifying the implementation of the problem definition, while Greedy simplifies the solution but disregarding a complex decomposition of the solution Computer Algorithms A Greedy Approach - a good example
Minimal ● Giving a set of possible coins and a target
Number of amount generate the minimal sized set of coins that adds up this amount Coins ● At every step try to remaining coin put the largest 81 25 amount coin 56 25 ● For example, how to minimally add 31 25 up 81 cents? 6 5 ● 5 coins 1 1 Computer Algorithms A bad example remaining coin Minimal ● Things can go very 81 25 Number of wrong for some amounts and set of 56 25 Coins possible coins 31 25 ● At every step try to put the largest 6 1 amount coin 5 1 ● For example, how 4 1 to minimally add up 81 cents? 3 1 ● 9 coins 2 1
1 1 Computer Algorithms A Non Greedy Approach
Minimal ● Let's say you can try a better solution
Number of exhaustively (for example, Brute Force) to find an optimal solution Coins ● Try all combinations remaining coin deriving changes from 81 25 the Greedy changing a choice at a time 56 25
● For example, how 31 10
to minimally add 21 10 up 81 cents? ● 6 coins 11 10
1 1 Examples The problem
Egyptian ● Any irreducible rational number (a number that can
Fractions be expressed in a ratio of two Integers that are not multiples) can be expressed as a sum of unit fractions (rational number where the numerator is 1) ○ For example: ⅚ = ½ + ⅓ ● This is a very old problem that was as the name says very much used by the old Egyptians ○ Solutions for this problem were introduced by Leonardo Fibonacci in 1202 ■ For example 7/15 = 1/3 + 1/8 + 1/120
Among the possible solutions, Fibonacci's
Greedy Algorithm was the best solution Examples The solution - A Greedy Approach
Egyptian ● Starts with the largest possible fitting unit fraction, than Fractions deal with the remainder (recursively) ○ For example: 7/15 ■ ½ won't fit, ⅓ fits! ○ 7/15 = 1/3 + ? => 7/15 = 5/15 + 2/15 ■ Apply it to 2/15: ● ½, ⅓, ¼, ⅕, ⅙, and 1/7 won't fit, ⅛ fits! ○ 7/15 = 1/3 + 1/8 + ? => 56/120 = 40/120 + 15/120 + 1/120 ■ Apply it to 1/120 (elementary solution) ○ 7/15 = 1/3 + 1/8 + 1/120 (final solution) Examples The Greedy solution - Python implementation
Egyptian Fractions
● The ceiling function to find the larger
denominator fitting is the basic Greedy operation Examples The Greedy solution - Python implementation
Egyptian Fractions
● The egyptian(n, d) function is repeatedly called
● Full code available here Greedy Algorithms Task #1 for this week's In-class exercises ● Run the Egyptian Fractions for the following Egyptian examples:
Fractions ○ 5/6, 7/15, 23/34, 121/321, 5/123
○ Write remarks in your new code with the solution of such cases
Go to IDLE and edit the code with the required remarks
Save your program in a .py file and submit it in the appropriate delivery room
Deadline: This Friday 11:59 PM EST
Examples Limits of the Implementation
Egyptian Fractions
● The precision of the operation n = x * n - d
● Try it out for the fraction 5/121 Greedy Algorithms Task #2 for this week's In-class exercises ● Run the Egyptian Fractions for the following Egyptian example 5/121 using the code
Fractions ○ Check it out manually the expected result,
which should be:
Write it down why you think it didn't work as intended
Save your text in a file and submit it in the appropriate delivery room
Deadline: This Friday11:59 PM EST
Examples Limits of the Approach
Egyptian ● The fraction 5/121 if computed correctly should Fractions be
● A better solution could be
● Remember 1/25 is larger than 1/33 …
Examples The Problem
Knapsack ● Given a set of items i with a weight wi and an
associated value vi Problem ● Given a knapsack with a limited weight capacity ● Which items can be stored in the knapsack carrying the maximum overall value? ○ Formal definition from Wikipedia here ○ Several problems (including the minimal number of coins) are variations of the knapsack problem ● While the optimal solution is not known, the Greedy Algorithms delivers reasonable results Examples The Solution - Brute Force approach
Knapsack ● Generate all possible combinations of items
○ If the problem is unbounded (any number of Problem object is available) keep on piling up objects until the overall weight is about to be exceed ● Keep checking the maximum value of each combination ○ Optimal solution, but a very high cost to generate all possible combinations ● This kind of problem complexity is not possible to be described by a polynomial formula ○ Therefore it is called a Nondeterministic Polynomial (NP) problem, and this has been formally proved ■ A NP-complete problem Examples The Solution - Greedy approach
Knapsack Problem ● Compute item's ratio between weight and value ● Sort the elements by the ratio (non decrescent) ● Repeatedly pick the item with highest ratio that fits the maximum weight capacity Examples The Solution - Greedy approach
Knapsack Problem ● Get the number of items, plus their value and weight ● Get the capacity ● Call knapsack
Full code here
Greedy Algorithms Task #3 for this week's In-class exercises ● Run the Knapsack Greedy code for the following Knapsack cases (list of items - [value,weight])
Go to IDLE and edit the code with the required remarks
Save your text in a file and submit it in the appropriate delivery room
Deadline: This Friday11:59 PM EST
Greedy Algorithms Task #4 for this week's In-class exercises ● Come up with one additional knapsack test case Knapsack of your own. It must result in more than one type of item being placed in the knapsack. Code it in Problem your .py file after task 3. Be sure to indicate the expected result.
Go to IDLE and edit the code with the required remarks
Save your text in a file and submit it in the appropriate delivery room
Deadline: This Friday11:59 PM EST
Examples The Limits of the Approach
Knapsack ● Trying it out for:
○ ([5,25] [6,36] [7,49] [8,64]) - capacity 72 Problem ■ The program delivers: ● 2 [5,25] items - Value: 10, Weight: 50 ■ A best solution would be: ● 2 [6,36] items - Value: 12, Weight: 72 ● The limitation usually appears when the answer is a small number of items, as small grain problems are usually effectively handled by Greedy ● There is a Dynamic programming algorithm that is more stable to deliver good solutions Greedy Algorithms Project #4 - this week's Assignment Fourth ● Create a program that receives the list of possible Assignment named items with the following information: ○ Value ($), Height (in), Width (in), Depth (in) ● The limit of the optimal solution is expressed by the volume in cubic inches (in3) and the program has to maximize the value within the cubic limit ● Your program should read textual file with one item kind per line with the information separated by comma, for example this file lists four items with values 35, 40, 45, and 58 dollars and increasing dimensions ● Your program should read any file with this format (name,value,height,width,depth) per line Greedy Algorithms Project #4 - this week's Assignment ● This program must be your own, do not use someone else’s code Fourth ● Any specific questions about it, please bring to the Office hours meeting this Assignment ● Friday or contact me by email This is a challenging program to make sure you are mastering your Python programming skills, as well as your asymptotic analysis understanding ● Don’t be shy with your questions Go to IDLE and try to program it Save your program in a .py file and submit it in the appropriate delivery room
Deadline: Next Tuesday11:59 PM EST
That’s all for today folks!
This week’s tasks Next week
● Discussion: initial post by this Friday/replies by ● Amortized next Tuesday algorithms ● Tasks #1, #2, #3 and #4 for the In-class exercises ○ Deadline: Friday 11:59 PM EST ● Quiz #4 to be available this Friday ● Don’t let work pile ○ Deadline: Next Tuesday 11:59 PM EST up! ● Project #4 assignment ● Don’t be shy about ○ Deadline: Next Tuesday 11:59 PM EST your questions
● Try all exercises seen in class and consult the
reference sources, as the more you practice, the easier it gets
