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 > v2 > > vr for r coins types, where each coins 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 cashiers algorithm. Consider the following pseudocodemeant to implement the cashiers algorithmwhere 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 d

This 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 cashiers 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 vi > 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, d; = k and where k is minimized, and such that the sum of the values id;v; = 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 >O{ k = r while (k > 0 and v[k] >n) { k++ } if k==0 { return 'no solution' } else { n = n - v[k] } return d This 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) 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 vi > 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, d; = k and where k is minimized, and such that the sum of the values id;v; = 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 >O{ k = r while (k > 0 and v[k] >n) { k++ } if k==0 { return 'no solution' } else { n = n - v[k] } return d This 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) 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