CSE 101 Homework 4 Dynammic Programming Due Thursday June 4 100 points total 10 Gizmos Consider the following problem You wish to purchase at least n identical gizmos Gizmos come in packages of different sizes and different prices You can buy any number of packages of each size as long as the total number is at least n You wish to find the minimum total price of such a set of packages The input is given as n and an array P ackages 1 m where each P ackage i has a positive integer field P ackage i size and a positive real field P ackage i price giving the number of gizmos in the package and the price of the package A recursive algorithm to solve this problem is BestPrice n positive integer Packages 1 m array of pairs size integer price real 1 M inP rice inf 2 For d 1 to m do 3 begin 4 5 IF P ackages d size n THEN T empP rice P ackages d price ELSE T empP rice P ackages d price BestP rice n P ackages d size P ackages 6 IF T empP rice M inP rice THEN M inP rice T empP rice 7 end 8 Return M inP rice Part 1 2 points Show the recursion tree of the above algorithm on the following input n 6 packages buy 5 for 12 3 for 8 or 2 for 6 Case 1 Buy package of 5 Cost 12 BestPrice 1 Packages Case 1a Buy package of 5 1 Cost 12 Case 1b Buy package of 3 1 Cost 8 Case 1c Buy package of 2 1 Cost 6 Minimum 6 Case 1 returns 12 6 18 Case 2 Buy package of 3 Cost 8 BestPrice 3 Packages Case 2a Buy package of 5 3 Cost 12 Case 2b Buy package of 3 3 Cost 8 Case 2c Buy package of 2 Cost 6 BestPrice 1 Packages Case 2cI Buy package of 5 1 Cost 12 1 Case 2cII Buy package of 3 1 Cost 8 Case 2cIII Buy package of 2 1 Cost 6 Minimum 6 Case 2c returns 6 6 12 Minimum for Case 2 is 8 Case 2 returns 8 8 16 Case 3 Buy package of 2 Cost 6 BestPrice 4 Packages Case 3a Buy package of 5 4 Cost 12 Case 3b Buy package of 3 Cost 8 BestPrice 1 Packages Case 3bI Buy package of 5 1 Cost 12 Case 3bII Buy package of 3 1 Cost 8 Case 3bIII Buy package of 2 1 Cost 6 Minimum 6 Case 3b returns 8 6 14 Case 3c Buy package of 2 Cost 6 BestPrice 2 Packages Case 3cI Buy package of 5 2 Cost 12 Case 3cII Buy package of 3 2 Cost 8 Case 3cIII Buy package of 2 2 Cost 6 Minimum 6 Case 3b returns 6 6 12 Case 3 minimum is 12 Case 3 returns 6 12 18 Overall minimum is Case 2 16 which is returned by the main procedure Part 2 3 points Give a bound on the worst case number of recursive calls the recursive algorithm could make in terms of n and m There are at most m recursive calls and each reduces the value of n by at least 1 This gives a tree of fan out m and depth at most n so a total of O mn recursive calls Assume all packages have distict sizes If not we could just delete all but the least expensive package of a given size Then we make in terms of n T n T n size1 T n size2 T n sizem T n 1 T n 2 We can use induction to prove T n O 2n See last answer key Part 3 10 points Give a dynammic programming version of the recurrence Note that only the value of n not the set of Packages changes in recursive calls and that takes on values from 1 n Also n decreases in each recursive call So we should fill in an array of one dimension of size n in increasing order of n This leads to DPBestPrice n positiveinteger P ackages 1 m array of pairs size integer price real 1 Initialize M P 1 n 2 FOR N 1 to n do 2 3 4 5 6 M inP rice inf FOR d 1 to m do IF P ackages d size N THEN T empP rice P ackages d price ELSE T empP rice P ackages d price M P N P ackages d size 7 IF T empP rice M inP rice THEN M inP rice T empP rice 8 M P N M inP rice 9 Return M P n Part 4 3 points Give a time analysis of this dynammic programming algorithm in terms of n and m There are two nested loops one going from 1 to n the other from 1 to m which gives a total time of O nm Part 5 2 points Show the array that your algorithm produces on the above example 1 2 3 4 5 6 6 min 6 8 12 6 min 6 8 12 8 min 6 MP 1 12 8 12 12 min 6 MP 2 12 8 MP 1 14 12 12 min 6 MP 3 14 8 MP 2 14 12 16 min 6 MP 4 18 8 MP 3 16 12 MP 1 18 For each of the following three problems describe the fastest dynamic programming algorithm you can find and give a time analysis in terms on any of the given parameters One Dimensional Clustering 20 pts You are given n real numbers r1 r2 rn and an integer 1 k n You want to find k disjoint intervals I1 a1 b1 I2 a2 b2 Ik ak bk so that each ri Ij for some j in a way the sum of the squares of the length of the intervals Pj kthat minimizes 2 b a j j j 1 We can give a recursion based on the question where does the first cluster end Let s assume the numbers are sorted from smallest to largest If not we sort them in O n log n time using mergesort BTClusters R 1 n k 1 IF k n return 0 2 IF k 1 return R n R 1 2 Only choice is cluster R 1 R n 3 Best 4 FOR I 1 to n do 3 5 6 T hisCost R I R 1 2 BT Clusters R I 1 n k 1 Case when first cluster is R 1 R I IF T hisCost Best THEN Best T hisCost 7 Return Best The sub problems we solve are of the form BT Clusters R J n K where 1 J n and 1 K k So we will use a n by k matrix C I K to hold BT Clusters R J n K K decreases as we make recursive calls so we fill this matrix in increasing value of K DPClusters R 1 n k 1 Initailize C 1 …