Question 4

V=[1, 2, 6, 12, 24, 48, 60] with A=[2000, 2001, 2002, ..., 2200]

V=[1, 2, 6, 12, 24, 48, 60] 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,2,6,12,24,48,60] IS NOT 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 NOT equal to DP (or Slow) for all values of A that were plotted for this coin system. There are multiple values of A between 2000 and 2200 for which greedy is sub-optimal.

V=[1, 6, 13, 37, 150] with A=[2000, 2001, 2002, ..., 2200]

V=[1, 6, 13, 37, 150] 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,6,13,37,150] IS NOT 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 NOT equal to DP (or Slow) for all values of A that were plotted for this coin system. There are multiple values of A between 1 and 30 and between 2000 and 2200 for which greedy is sub-optimal.