Homework Assignment #16

Objective

To solve an instance of the optimal coin change problem using dynamic programming where a greedy algorithm would fail.

Exercises

Show all work neatly.

Question 1

Now consider a coin system for which we know the greedy algorithm would fail to always provide optimal change: $d=[1,5,8]$. Show how to use dynamic programming to optimally make change for 10 units.

Question 2

Yes or No: Did you read all of Section 6.3 in the textbook?