Chapter 5 Fundamental Algorithm Design Techniques Overview The Greedy Method 5 1 Divide and Conquer 5 2 Dynamic Programming 5 3 Greedy Outline The Greedy Method Technique 5 1 Fractional Knapsack Problem 5 1 1 Task Scheduling 5 1 2 Minimum Spanning Trees 7 3 future lecture A New Vending Machine A new Coke machine in the lounge behind the ulab Being efficient computer scientists we want to return the smallest possible number of coins in change The Greedy Method The Greedy Method The greedy method is a general algorithm design paradigm built on the following elements configurations different choices collections or values to find objective function a score assigned to configurations which we want to either maximize or minimize It works best when applied to problems with the greedy choice property a globally optimal solution can always be found by a series of local improvements from a starting configuration Making Change Problem A dollar amount to reach and a collection of coin amounts to use to get there Configuration A dollar amount yet to return to a customer plus the coins already returned Objective function Minimize number of coins returned Greedy solution Always return the largest coin you can Example 1 Coins are valued 32 08 01 Has the greedy choice property since no amount over 32 can be made with a minimum number of coins by omitting a 32 coin similarly for amounts over 08 but under 32 Example 2 Coins are valued 30 20 05 01 Does not have greedy choice property since 40 is best made with two 20 s but the greedy solution will pick three coins which ones How to rob a bank The Fractional Knapsack Problem Given A set S of n items with each item i having bi a positive benefit wi a positive weight Goal Choose items with maximum total benefit but with weight at most W If we are allowed to take fractional amounts then this is the fractional knapsack problem In this case we let xi denote the amount we take of item i Objective maximize b x w i i S Constraint x i i S W i i Example Given A set S of n items with each item i having bi a positive benefit wi a positive weight Goal Choose items with maximum total benefit but with weight at most W knapsack Items Weight Benefit Value per ml 1 2 3 4 Solution 5 4 ml 8 ml 2 ml 6 ml 1 ml 12 32 40 30 50 3 4 20 5 50 10 ml 1 2 6 1 ml ml ml ml of of of of 5 3 4 2 The Fractional Knapsack Algorithm Greedy choice Keep taking item with highest value benefit to weight ratio Since bi xi wi bi wi xi i S i S Run time O n log n Why Correctness Suppose there is a better solution there is an item i with higher value than a chosen item j but xi wi xj 0 and vi vj If we substitute some i with j we get a better solution How much of i min wi xi xj Thus there is no better solution than the greedy one Algorithm fractionalKnapsack S W Input set S of items w benefit bi and weight wi max weight W Output amount xi of each item i to maximize benefit w weight at most W for each item i in S xi 0 vi bi wi value w 0 total weight while w W remove item i w highest vi xi min wi W w w w min wi W w Task Scheduling Given a set T of n tasks each having A start time si A finish time fi where si fi Goal Perform all the tasks using a minimum number of machines Machine 3 Machine 2 Machine 1 1 2 3 4 5 6 7 8 9 Task Scheduling Algorithm Greedy choice consider tasks Algorithm taskSchedule T by their start time and use as Input set T of tasks w start time si few machines as possible with and finish time fi this order Output non conflicting schedule Run time O n log n Why with minimum number of machines Correctness Suppose there is a m 0 no of machines better schedule while T is not empty We can use k 1 machines remove task i w smallest si The algorithm uses k if there s a machine j for i then Let i be first task scheduled on machine k schedule i on machine j Machine i must conflict with else k 1 other tasks m m 1 But that means there is no schedule i on machine m non conflicting schedule using k 1 machines Example Given a set T of n tasks each having A start time si A finish time fi where si fi 1 4 1 3 2 5 3 7 4 7 6 9 7 8 ordered by start Goal Perform all tasks on min number of machines Machine 3 Machine 2 Machine 1 1 2 3 4 5 6 7 8 9 Divide and Conquer 7 2 9 4 2 4 7 9 7 2 2 7 7 7 2 2 9 4 4 9 9 9 4 4 Outline and Reading Divide and conquer paradigm 5 2 Review Merge sort 4 1 1 Recurrence Equations 5 2 1 Iterative substitution Recursion trees Guess and test The master method Integer Multiplication 5 2 2 Divide and Conquer Divide and conquer is a general algorithm design paradigm Divide divide the input data S in two or more disjoint subsets S1 S2 Recur solve the subproblems recursively Conquer combine the solutions for S1 S2 into a solution for S The base case for the recursion are subproblems of constant size Analysis can be done using recurrence equations Binary Search I have a number X between c1 and c2 Divide and conquer algorithm Analysis b T n T n 2 c if n 2 if n 2 Called a Recurrence Equation How to solve Solving the Binary Search Recurrence T n T n 2 c T n 2 T n 4 c T n 4 T n 8 c T n T n 2 c T n 4 c c T n 22 2 c T n 23 3 c telescope T n 2k k c done when k lg n then T n 2k T 1 is base case b c lg n Merge Sort Recurrence Equation Analysis Recurrence Equation b T n 2T n 2 bn if n 2 if n 2 We can analyze by finding a closed form solution Method expand and telescope Solving the Merge Sort recurrence T n 2T n 2 b n T n 2 2T n 4 b n 2 T n 4 2T n 8 b n 4 T n 2T n 2 b n 2 2T n 4 b n 2 b n 22T n 22 2 b n 23T n 23 3 b n telescope 2kT n 2k k b n done when k lg n then T n 2k T 1 is base case b n …