Algorithms Problem:

The link is just to a Google search for "euro coin denominations"

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 vv2>... vr for r coins types, where each coin's value v is a positive integer. His goal is to obtain a set of counts {di), 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 is a vector of the coin denominations: wizardChange (n,v,r): // initial histogram of coin types in solution while n 0 f while k> 0 and v[k]>n k++ if k 0 return 'no solution' else n = n-v [k] } 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 herefo hich 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 vv2>... vr for r coins types, where each coin's value v is a positive integer. His goal is to obtain a set of counts {di), 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 is a vector of the coin denominations: wizardChange (n,v,r): // initial histogram of coin types in solution while n 0 f while k> 0 and v[k]>n k++ if k 0 return 'no solution' else n = n-v [k] } 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 herefo hich 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.)