COMPUTER SCIENCE TRIPOS Part II – 2016 – Paper 7
Advanced Algorithms (TMS)
(a) State the zero-one principle in the context of sorting networks. [2 marks]
(b) For each of the following six comparison networks, state whether it is a sorting
network or not. In each case, justify your answer. For the justification you may
refer to standard results without giving a proof. [9 marks]
(1) (2) (3)
(4) (5)
(6)
(c) Let n be an exact power of 2. Show how to construct an n-input, n-output
comparison network of depth log n in which the top output wire always carries
the minimum input value and the bottom output wire always carries the
maximum input value. [4 marks]
(d) (i) Prove that the number of comparators in any sorting network is Ω(n log n).
[4 marks]
(ii) What does Part (d)(i) imply in terms of the depth of any sorting network?
[1 mark]