1. Consider the problem of returning change to a customer requiring the smallest number of coins....

2.  
3. 
   

Transcribed Image Text:

1. Consider the problem of returning change to a customer requiring the smallest number of coins. a. Show that the greedy algorithm given below returns the smallest number of coins for the coin set {1,5, 10, 25}. Procedure Greedy (C: change amount) Arrays c and a are global variables. c[i] amount of coin type i (c[i]> c[i+1]) x[i] solution number of coins of type i in solution (initially x[i] = 0) begin if C 0 then return else begin i = 1; while c[i]>C doi = i + 1; x[i] = x[i] + 1; C=C c[i]; Greedy(C); end; end. b. Does the algorithm compute the correct answer for all coin types? 1. Consider the problem of returning change to a customer requiring the smallest number of coins. a. Show that the greedy algorithm given below returns the smallest number of coins for the coin set {1,5, 10, 25}. Procedure Greedy (C: change amount) Arrays c and a are global variables. c[i] amount of coin type i (c[i]> c[i+1]) x[i] solution number of coins of type i in solution (initially x[i] = 0) begin if C 0 then return else begin i = 1; while c[i]>C doi = i + 1; x[i] = x[i] + 1; C=C c[i]; Greedy(C); end; end. b. Does the algorithm compute the correct answer for all coin types?