COMPUTER SCIENCE TRIPOS Part IA – 2019 – Paper 1
Algorithms (fms27)
(a) The Post Office of Maldonia issued a new series of stamps, whose denominations
in cents are a finite set D ⊂ N\{0}, with 1 ∈ D. Given an arbitrary value
n ∈ N\{0} in cents, the problem is to find a minimum-cardinality multiset of
stamps from D whose denominations add up to exactly n.
In the context of solving the problem with a bottom-up dynamic programming
algorithm. . .
(i) Give and clearly explain a formula that expresses the optimal solution in
terms of optimal solutions to subproblems. [Note: If your formula gives
only a scalar metric (e.g. the number of stamps) rather than the actual
solution (e.g. which stamps), please also explain how to obtain the actual
optimal solution.] [4 marks]
(ii) Draw and explain the data structure your algorithm would use to
accumulate the intermediate solutions. [2 marks]
(iii) Derive the big-Theta space and time complexity of your algorithm.
[1 mark]
(b) Repeat (a)(i)–(a)(iii) for the following problem:
A car must race from point A to point B along a straight path, starting with a
full tank and stopping as few times as possible. A full tank lets the car travel
a given distance l. There are n refuelling stations so ≡ A, s1, s2, . . . , sn ≡ B
along the way, at given distances d0 = 0, d1, d2, . . . , dn from A. The distance
between adjacent stations is always less than l. The problem is to find a
minimum-cardinality set of stations where the car ought to refill in order to
reach B from A. [7 marks]
(c) Which of the two previous problems might be solved more efficiently with a
greedy algorithm? Indicate the problem and describe the greedy algorithm.
Then give a clear and rigorous proof, with a drawing if it helps clarity, that your
greedy algorithm always reaches the optimal solution. Derive the big-Theta time
complexity. [6 marks]