Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 4 / c / Solution

In the coin change problem, take denominations $\{1,3,4\}$ and target amount $6$. The natural greedy algorithm repeatedly chooses the largest denomination not exceeding the remaining amount. It chooses $4$, then $1$, then $1$, for three coins. Yet $3+3=6$ uses only two.

Two is optimal: one coin cannot make $6$ because denomination $6$ is absent, and the displayed pair attains the lower bound. ThereforeThe locally largest first coin loses the possibility of using the better pair of threes. This supplies a concrete failure of the greedy-choice property; optimal substructure alone does not justify the greedy choice. The dynamic programming recurrence from part (b) would compare all feasible first or last denominations and find the pair.