COMPUTER SCIENCE TRIPOS Part IA – 2014 – Paper 1
Algorithms (FMS)
(a) Explain an efficient method to find the k-th smallest number in a set of n
numbers (output: one number), without first sorting the n numbers, and discuss
its complexity in terms of n and k. [4 marks]
(b) Explain an efficient method to find the k smallest numbers in a set of n numbers
(output: k numbers), without first sorting the n numbers, and discuss its
complexity in terms of n and k. How much extra work is needed compared
to (a)? [4 marks]
(c) Draw four distinct binary search trees (BSTs) for the following set of keys:
{1, 2, 3, 4}. [2 marks]
(d) Let a height-balanced BST (hBST) be a BST with the additional defining
invariant that each node is the parent of subtrees whose heights differ by at
most 1. Give an efficient procedure to insert into an hBST and prove that the
defining invariant is preserved. [10 marks]