Question 3

V=[1, 5, 10, 25, 50] with A=[2010, 2015, 2020, ..., 2200]

V=[1, 5, 10, 25, 50] with A=[1, 2, 3, ..., 30]

Note that the "changeslow" algorithm had to be run for $A < 30$ due to extremely long running times. The plots above suggest that the coin system [1,5,10,25,50] may be canonical[1]. A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts. Our observations show that greedy is equal to DP (and Slow) for all values of A that were plotted for this coin system.