Question 6

Question 3 Runtime plots

Runtime Plots for the Slow, DP, and Greedy Algorithms

Note that the "changeslow" algorithm had to be run for a smaller range of $A$ due to extremely long running times.

Greedy Fit Curve Equation:

$$y = 3.2995 * 10^{-9} * x + 1.0700 * 10^{-5}$$

Dynamic Programming Fit Curve Equation:

$$y = 1.05375 * 10^{-6} * x - 3.46787 * 10^{-5}$$

Slow Fit Curve Equation:

$$y = 2.18862 * 10^{-7} * e^{0.7136x} + 0.0002267$$

Runtime Plot for the Slow, DP, and Greedy Algorithms

Question 4 Runtime Plots

Runtime Plots for the Slow, DP, and Greedy Algorithms Part A

Note that the "changeslow" algorithm had to be run for a smaller range of $A$ due to extremely long running times.

Greedy Fit Curve Equation:

$$y = 2.6146 * 10^{-9} * x + 1.77676 * 10^{-5}$$

Dynamic Programming Fit Curve Equation:

$$y = 1.2664 * 10^{-6} * x + 0.001705$$

Slow Fit Curve Equation:

$$y = 1.51844 * 10^{-7} * e^{0.701x} + 5.2627 * 10^{-5}$$

Runtime Plot for the Slow, DP, and Greedy Algorithms Part A

Runtime Plots for the Slow, DP, and Greedy Algorithms Part B

Note that the "changeslow" algorithm had to be run for a smaller range of $A$ due to extremely long running times.

Greedy Fit Curve Equation:

$$y = 1.0347 * 10^{-9} * x + 5.740 * 10^{-6}$$

Dynamic Programming Fit Curve Equation:

$$y = 1.02725 * 10^{-6} * x + 0.00146$$

Slow Fit Curve Equation:

$$y = 2.252 * 10^{-7} * e^{0.7072x} + 0.000162$$

Runtime Plot for the Slow, DP, and Greedy Algorithms Part B

Question 5 Runtime Plots

Runtime Plots for the Slow, DP, and Greedy Algorithms

Greedy Fit Curve Equation:

$$y = 5.43669 * 10^{-9} * x + 8.425 * 10^{-6}$$

Dynamic Programming Fit Curve Equation:

$$y = 2.4784 * 10^{-6} * x - 0.0041$$

Slow Fit Curve Equation:

$$y = 0.00013 * e^{0.175x} - 0.001122$$

As we can see in the plots above the best fitting curves are linear for the greedy and dynamic programming cases and exponential for the slow case. The trends observed by the fit lines match what we would expect from our runtime analysis whereby the greedy has a theoretical runtime of $O(n + k)$, the dp has a theoretical runtime of $O(n * k)$ and the slow has a theoretical runtime of $O(3^{n})$. The greedy and dynamic programming runtimes are observed to be linear because $k$ (length of the coin denominations array) is held constant while $n$ (the change amount) is varying, therefore the experimental curves are still consistent the theoretical runtimes. In Question 5, the curve fit of the slow algorithm is slightly degraded by the fact that all even values of $A$ bypass the exponential behavior due to the change being made in a single coin. This is evident by the run time for even values of $A$ being approximately 0. If a curve fit was drawn through the odd values of $A$, it would match the behavior from Q3/Q4a/Q4b.