In this question we consider the change-making problem (as covered in recitation), of making change for n cents using the smallest number of coins. Suppose we have coins with denominations of v1 > v2 > · · · > vr for r coins types, where each coin’s value vi is a positive integer. Your goal is to obtain a set of counts {di}, one for each coin type, such that Pr i=1 P di = k and where k is minimized, and such that the sum of the values r i=1 divi = n. (a) A greedy algorithm for making change is the cashier’s algorithm. Consider the following pseudocode—meant to implement the cashier’s algorithm—where n is the amount of money to make change for and v is a vector of the coin denominations: change(n, v,r) : d[1 .. r] = 1 // initial histogram of coin types in solution while n > 0 { k = r while ( k > 0 and v[k] > n ) { k++ } if k==0 { return ‘no solution’ } else { n = n - v[k] } } return dThis code has bugs. Identify the bugs and explain why each would cause the algorithm to fail.(b) Identify a set of Euro coin denominations (a subset of the denominations here) 1 for which the greedy algorithm does not yield an optimal solution for making change. Justify your answer in terms of optimal substructure and the greedychoice property. (The set should include the 1 Euro cent so that there is a solution for every value of n.) Include an example where the cashier’s algorithm with your choice of denominations yields a set of coins that is larger than it needs to be, and also show the smaller set of coins adding up to the same value.