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 > 2> .> vr for r coins types, where each coin's value Vi is a positive integer. His goal is to obtain a set of counts (4), one for each coin type, such that di-k and where k is minimized (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 illustrate it, where n is the amount of money to make change for and v s a vector of the coin denominations: wizardChange(n,v,r) / nitial histogran of coin types in solution while n > 0 f while k > 0 and v[k] > n) 1 kt if k-0 return else {n=n-v[k] } no solution' > return d Hermione scoffs and says Malfoy's code has bugs. Identify the bugs and explain why each would cause the algorithm to fail. (b) (8 pts) Sometimes the goblins at Gringotts Wizarding Bank run out of coins and make change using whatever is left on hand. Identify a set of Euro coin denomi nations (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.)