Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / b

For nonnegative integer amount $v$, let $M[t]$ be the minimum number of coins making amount $t$. Set $M[0]=0$ and compute, in increasing order of $t$,An empty candidate set has minimum $\infty$. Here denomination $1$ ensures that every nonnegative amount is attainable. Removing one coin from an optimal nonempty solution gives a smaller amount, and adding any allowed last coin gives a feasible solution; these two directions prove the recurrence by induction on $t$.

Return whether $M[v]\le k$. This solves the at-most-$k$ decision without needing a separate dimension for $k$. The table for the minimum coin change recurrence takes $O(nv)$ running time and $O(v)$ space complexity. The bound is pseudopolynomial time: the amount, rather than its binary encoding length, appears in it. Amount zero needs zero coins.

During the computation in part i, record an index $\mathrm{last}[t]$ attaining the minimum at every positive amount. Starting with $t=v$, print $x_{\mathrm{last}[t]}$ and replace $t$ by $t-x_{\mathrm{last}[t]}$, continuing until $t=0$.

Every step decreases the amount and reduces the table entry by exactly one. The printed denominations therefore sum to $v$ and their number is exactly $M[v]$, proving optimality. The total running time is $O(nv+M[v])$, including the output; $M[v]\le v$ because denomination $1$ is available. The predecessor array adds $O(v)$ to the space complexity. This is reconstruction from the dynamic programming certificate, not the largest-denomination greedy algorithm, which need not be optimal for arbitrary denominations.

Let $M_i[t]$ use only the first $i$ available coins. Initialize $M_0[0]=0$, $M_0[t]=\infty$ for $t>0$, and useomitting the second term when $t<x_i$. The alternatives exclude the current coin or use it once; both refer to the previous row, so it cannot be used twice. Induction on $i$ proves correctness, and $M_n[v]$ is the required answer, including $\infty$ when no selection works.

The running time is $O(nv)$. A single amount array reduces auxiliary space to $O(v)$ if each coin updates amounts in descending order, $t=v,v-1,\dots ,x_i$. Then $M[t-x_i]$ still describes the previous row. Ascending updates would reuse the same coin and solve a different, unlimited-supply problem.