Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 8

For denominations $1,3,4$ and target $6$, greedy selects $4+1+1$, using three coins. The representation $3+3$ uses two coins and is optimal because there is no denomination six. Hence choosing the largest affordable coin is not generally optimal.

Write $c_j=2^j+1$ for $0\le j\le k$, with a separate unit denomination. Choose, among all minimum-coin representations of the target, one whose vector of counts is lexicographically largest when larger denominations come first. Such a choice exists because a fixed positive target has only finitely many representations.

There cannot be two unit coins: replacing them by one $c_0=2$ decreases the count. For $j<k$, two copies of $c_j$ can be exchanged usingThis keeps the coin count unchanged but increases the first differing larger-denomination count, contradicting the chosen lexicographic maximum. Thus there exists an optimal representation using at most one of each denomination below the largest. The largest denomination may repeat.

It remains to show why that normalization implies greedy optimality; uniqueness alone is not enough for an arbitrary coin system. Fix a denomination $c_j$. Let $L$ be the total value of all coins smaller than $c_j$ in the chosen optimal representation, and let $r$ be their number. These smaller coins are distinct. If $I\subseteq \{0,\dots ,j-1\}$ records the selected non-unit denominations, thenIf $L\ge c_j$, replace all $r$ smaller coins by one $c_j$ and $L-c_j$ unit coins. The new number of coins iscontradicting optimality. Therefore the total value below every denomination $c_j$ is strictly less than $c_j$.

At the largest denomination, this forces its count to be $\lfloor n/c_k\rfloor$: its residual value is nonnegative and smaller than $c_k$. Remove those coins. The same smaller-denomination property then forces the next quotient, and so on down to the unit coin. These are exactly greedy's choices, proving greedy is optimal for every positive target. The argument also covers $k=0$, where the denominations are two and one. Independent comparison with coin-change dynamic programming confirmed the formula for all $0\le k\le 8$ and targets from one to 2,000; that finite check supplements the proof.

Serve customers in nondecreasing service time, with ties broken arbitrarily. The objective in the source includes each customer's own service time, so these are completion times, not only delays before service begins. If the order is $\sigma$, thenTo prove optimality, consider adjacent service times $a>b$ after an elapsed time $P$. Their contributions before an exchange are $(P+a)+(P+a+b)$; after the exchange they are $(P+b)+(P+b+a)$. The total decreases by $a-b>0$. Earlier customers are unaffected, and later customers begin after the same combined duration $a+b$ as before, so their completion times are unchanged.

Repeatedly exchanging adjacent inversions reaches a nondecreasing order without increasing the objective. Hence that order is optimal. Sorting takes $O(n\log n)$ time in a comparison model, followed by a linear traversal to produce the order or compute the total. Equal service times give zero exchange difference and do not affect optimality. If waiting time were instead defined before service, subtracting the order-independent total service time would give the same optimal order.