6. Consider a money change problem in which all denominations are powers of b (e.g. b^0,...

 

Transcribed Image Text:

6. Consider a money change problem in which all denominations are powers of b (e.g. b^0, b^1,.., b^k). In your change drawer, you have a finite number of each denomination d1, d2, ..., dm. The quantity of each denomination is designated as q1,q2,.... qm. a) Write the recursive solution to minimize the number of bills/coins to make change valued at n. b) Prove the greedy choice property. 7. Write the algorithm to solve the money change problem above. Identify the runtime and briefly justify. 6. Consider a money change problem in which all denominations are powers of b (e.g. b^0, b^1,.., b^k). In your change drawer, you have a finite number of each denomination d1, d2, ..., dm. The quantity of each denomination is designated as q1,q2,.... qm. a) Write the recursive solution to minimize the number of bills/coins to make change valued at n. b) Prove the greedy choice property. 7. Write the algorithm to solve the money change problem above. Identify the runtime and briefly justify.