only problem (b)

1. 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 > U2 > ... > Ur for r coins types, where each coin's value vi is a positive integer. Your goal is to obtain a set of counts {d}}, one for each coin type, such that i-di = k and where k is minimized, and such that the sum of the values - div; = 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 no{ k = r while (k> 0 and v[k] >n) { k++ } if k==0 { return 'no solution' } else { n = n - v[k] } return d (b) Identify a set of Euro coin denominations (a subset of the denominations here) for which the greedy algorithm does not yield an optimal solution for making change. Justify your answer in terms of optimal substructure and the greedy- choice 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. 1. 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 > U2 > ... > Ur for r coins types, where each coin's value vi is a positive integer. Your goal is to obtain a set of counts {d}}, one for each coin type, such that i-di = k and where k is minimized, and such that the sum of the values - div; = 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 no{ k = r while (k> 0 and v[k] >n) { k++ } if k==0 { return 'no solution' } else { n = n - v[k] } return d (b) Identify a set of Euro coin denominations (a subset of the denominations here) for which the greedy algorithm does not yield an optimal solution for making change. Justify your answer in terms of optimal substructure and the greedy- choice 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