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]