CSE 101 Homework 4Dynammic ProgrammingDue Thursday, June 4100 points total = 10 %Gizmos Consider the following problem. You wish to purchase (at least) nidentical gizmos. Gizmos come in packages of different sizes and differentprices. You can buy any number of packages of each size, as long as thetotal number is at least n. You wish to find the minimum total price ofsuch 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].pricegiving 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. MinP rice ← inf;2. For d = 1 to m do:3. begin;4. IF P ackages[d].size ≥ n THEN T empP rice ← P ackages[d].price5. ELSE T empP rice ← P ackages[d].price +BestP rice(n − P ackages[d].size, P ackages);6. IF T empP rice < MinP rice THEN MinP rice ← T empP rice;7. end;8. Return MinP rice.Part 1: 2 points Show the recursion tree of the above algorithm on thefollowing 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:12Case 1b: Buy package of 3 ¿ 1. Cost:8Case 1c: Buy package of 2 ¿ 1. Cost:6Minimum: 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:12Case 2b: Buy package of 3 =3. Cost:8Case 2c: Buy package of 2. Cost:6+BestPrice(1,Packages)Case 2cI: Buy package of 5 ¿ 1. Cost:121Case 2cII: Buy package of 3 ¿ 1. Cost:8Case 2cIII: Buy package of 2 ¿ 1. Cost:6Minimum=6. Case 2c returns 6+6 =12. Minimum for Case 2 is 8.Case 2 returns 8+8=16Case 3: Buy package of 2. Cost: 6+BestPrice(4,Packages)Case 3a: Buy package of 5 ¿ 4. Cost:12Case 3b: Buy package of 3 . Cost:8+BestPrice(1,Packages)Case 3bI: Buy package of 5 ¿ 1. Cost:12Case 3bII: Buy package of 3 ¿ 1. Cost:8Case 3bIII: Buy package of 2 ¿ 1. Cost:6Minimum=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:12Case 3cII: Buy package of 3 ¿ 2. Cost:8Case 3cIII: Buy package of 2 =2 . Cost:6Minimum=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 pro-cedure.Part 2: 3 points Give a bound on the worst-case number of recursivecalls the recursive algorithm could make in terms of n and m.There are at most m recursive calls, and each reduces the value of nby at least 1. This gives a tree of fan-out m and depth at most n, soa total of O(mn) recursive calls.Assume all packages have distict sizes. (If not, we could just deleteall but the least expensive package of a given size.) Then we make interms 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 recur-rence.Note that only the value of n, not the set of Packages, changes inrecursive calls, and that takes on values from 1...n. Also, n decreasesin each recursive call. So we should fill in an array of one dimensionof 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 MP [1..n].2. FOR N = 1 to n do:23. MinP rice ← inf;4. FOR d = 1 to m do:5. IF P ackages[d].size ≥ N THEN T empP rice ← P ackages[d].price6. ELSE T empP rice ← P ackages[d].price +MP [N − P ackages[d].size];7. IF T empP rice < M inP rice THEN M inP rice ← T empP rice;8. MP [N] ← M inP rice.9. Return MP [n].Part 4: 3 points Give a time analysis of this dynammic programmingalgorithm, in terms of n and m.There are two nested loops, one going from 1 to n, the other from 1to m, which gives a total time of O(nm).Part 5: 2 points Show the array that your algorithm produces on theabove example.1. 6 =min(6,8,12)2. 6 = min (6, 8, 12)3. 8 = min (6+ MP[1]=12, 8, 12)4. 12 =min (6+MP[2]=12, 8+MP[1]=14, 12)5. 12 = min (6+MP[3]=14, 8+MP[2]=14, 12)6. 16 = min (6+MP[4]=18, 8+MP[3]=16, 12+MP[1]=18)For each of the following three problems, describe the fastest dynamicprogramming algorithm you can find, and give a time analysis (in termson any of the given parameters).One Dimensional Clustering: 20 pts You are given n real numbers r1, r2, ..., rnand 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∈ Ijfor some j, in away that minimizes the sum of the squares of the length of the intervals,Pj=kj=1(bj− aj)2.We can give a recursion based on the question, where does the first clusterend? Let’s assume the numbers are sorted from smallest to largest. (Ifnot, 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:35. T hisCost ← (R[I] − R[1])2+ BT Clusters[R[I + 1..n], k − 1]{Case when first cluster is (R[1], R[I]).}6. IF T hisCost < Best THEN Best ← T hisCost7. Return Best.The sub-problems we solve are of the form BT Clusters[R[J..n], K] where1 ≤ J ≤ n and 1 ≤ K ≤ k. So we will use a n by k matrix C[I, K] to holdBT Clusters[R[J..n], K]. K decreases as we make recursive calls so we fillthis matrix in increasing value of K.DPClusters[R[1..n],k].1. Initailize C[1..n, 1..k].2. FOR J = 1 to n do:3. C[J, 1] ← (R[n] − R[J])24. FOR K = 2 to k do:5. FOR J = 1 to n − K + 1 do:6. Best ← ∞7. FOR I = J to n do:8. T hisCost ← (R[I] − R[J])2+ C[J + 1, K − 1] {Case whenfirst cluster is (R[J], R[I]).}9. IF T hisCost < Best THEN Best ← T hisCost10. C[J, K] ← Best.11. Return C[1, k].The above algorithm takes time O(n2k) for the three nested loops.Library storage A library has n books that must be stored in alphabeticalorder on adjustable height shelves. Each book has a height and a thickness.The width of the shelf is fixed at W , and the sum of the thicknesses ofbooks on a single shelf must be at most W . The next shelf will be placed ontop, at a height equal to the maximum height of a book in the shelf. Givean algorithm that minimizes the total height of shelves used to store all thebooks. You are given the list of books in