A greedy algorithm for making change is the cashier\'s algorithm, which all youn

Question

A greedy algorithm for making change is the cashier's algorithm, which all young wizards learn. Malfoy writes the following pseudocode on the whiteboard to illustrate it, where n is the amount of money to make change for and ? is a vector of the coin denominations: wizardChange(n, v): d[1 .. v.len()] =0//initial histogram of coin types in solution while n > 0 {k = r while (v[k] > n and k >= 0) {k--} if k==0 {return 'no solution'} else {d[k]++}} return d Hermione snorts and says Malfoy's code has bugs. Identify the bugs and explain why each would cause the algorithm to fail. (b) Sometimes the goblins at Gringotts Wizarding Bank run out of coins, and make change using whatever is left on hand. Identify a set of U.S. coin denominations for which the greedy algorithm does not yield an optimal solution. Justify your answer in terms of optimal substructure and the greedy-choice property. (The set should include a penny so that there is a solution for every value of n.)

Explanation / Answer

Answer of Part A)

The bugs are:

1. the value on n (total money) is never changed in the loop body. Hence, the loop will run infinitely and the code will never generete any solution.

2. The condition check "If..else" must be within the loop because at each iteration the algorithm must check whether the coins of a particular denomination is exhausted or not.

3. the variable r is not defined and had no use in the algorithm.

4. the condition of while must only check the total money is greater or equal to zero. the given condition is wrong.

Answer of Part B)

Let us consider a situation:

U.S. Postage: 1, 10, 21, 34, 70, 100, 350, 1225, 1500

Cashier's Algorithm 140 = 100 + 34 + 1 +1 + 1+ 1+ 1+ 1

Optimal solution 140 = 70 + 70

thus, the cashier algorithm does not give optimal solution in all cases.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.