(b) (8 pts) Sometimes the goblins at Gringotts Wizarding Bank run out of coins,1 and make change using whatever is left on hand. Identify a set of Euro coin denominations (a subset of the denominations here) 2 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.)

3. Draco Malfoy is struggling with the problem of making change for n cents using the smallest number of coins. Malfoy has coin values of vi > v2 > . . > vr for r coins types, where each coin's value vi is a positive integer. His goal is to obtain a set of counts {di}, di-k and where k is minimized one for each coin tvpe, such that (a) (7 pts) A greedy algorithm for making change is the cashier's algorithm, which all young wizards learn. Malfoy writes the following pseudocode on the white- board to 1llustrate it, where n is the amount of money to make change for and v is a vector of the coin denominations: wizardChange (n,v,r) : d[1 .. r] = 1 while n > 0 // initial histogram of coin types in solution while k > 0 and v[k] > n ) ( kt+h if k=-o { return 'no solution, } else n -n - v[k] h return d Hermione scoffs and says Malfoy's code has bugs. Identify the bugs and explain why each would cause the algorithm to fail