COMPUTER SCIENCE TRIPOS Part IA – 2014 – Paper 1
Algorithms (FMS)
(a) Consider the radix sort algorithm.
(i) Explain how radix sort works, to what inputs it can be applied and what
its asymptotic complexity is. [5 marks]
(ii) Explain why running radix sort does not proceed from most to least
significant digit, as would at first seem more intuitive. [4 marks]
(iii) Give a proof by induction of the correctness of radix sort. [4 marks]
(b) Clearly describe an algorithm, strictly better than O(n
2
), that takes a positive
integer s and a set A of n positive integers and returns a Boolean answer to the
question whether there exist two distinct elements of A whose sum is exactly s.
Evaluate its complexity. [7 marks]