COMPUTER SCIENCE TRIPOS Part IA – 2015 – Paper 1
Algorithms (FMS)
(a) Explain the greedy strategy in algorithm design. To what problems does it
apply? [3 marks]
(b) If a problem can be solved with both dynamic programming and a greedy
algorithm, what are the advantages of using one or the other? [2 marks]
(c) An imaginary post office machine must issue decorative stamps adding up to a
given amount of p pence. Its goal is to minimize the number of postage stamps
issued, and the machine always has as many stamps as needed.
(i) Let the set of available denominations for the stamps be D = {1p, 5p,
25p, 50p, £1, £2}. Can this problem be solved using bottom-up dynamic
programming? If so, clearly describe your algorithm and determine its
complexity. If not, prove that it cannot be done. [5 marks]
(ii) Let c1 < c2 < · · · < cn be n stamp denominations. Prove that if each ci (a
positive integer) is a multiple of ci−1 for every i = 2, . . . , n then the greedy
strategy applied to the set D = {c1, c2, · · · , cn} finds the optimal solution
for any amount p that is a multiple of c1. [7 marks]
(iii) Provide a set of denominations for stamps D and an amount of pence p
for which the greedy strategy fails to give an optimal solution, p being a
multiple of the smallest denomination in D. Show what solution the greedy
strategy would find and what the optimal solution is. [3 marks]