COMPUTER SCIENCE TRIPOS Part IA – 2014 – Paper 1
Algorithms (TMS)
(a) Explain the terms amortized analysis, aggregate analysis and potential method.
[6 marks]
(b) Consider an arbitrary sequence of n stack operations PUSH(), POP() and
MULTIPOP(x) in which POP() or MULTIPOP(x) never attempt to remove more
elements than there are on the stack. Assuming that the stack begins with
s0 items and finishes with sn items, determine the worst-case total cost for
executing the n operations as a function of n, s0 and sn. You may assume
PUSH() and POP() cost 1 each and MULTIPOP(x) costs x. [5 marks]
(c) Suppose we want to store a number of items in an array, but we do not know in
advance how many items need to be stored. The INSERT(x) operation appends
an item x to the array. More precisely, if the size of the array is large enough, x
is inserted directly at the end of the array. Otherwise, a new array of larger size
is created that contains all previous items with x being appended at the end.
The total cost of INSERT(x) is 1 in the first case, and the size of the new array
in the second case.
(i) Devise a strategy which, for any integer n, performs any sequence of n
INSERT(.) operations at a total cost of O(n). [5 marks]
(ii) For the strategy described in (c)(i), give a proof of the cost of the algorithm
using the potential method. [4 marks]