Description
1. Consider a comparison tree using 3-way comparisons that determines whether every input
sequence x1, x2, . . . , xn of n numbers contains a repetition.
(a) Prove that on the path from the root to a leaf taken by an input sequence of n distinct
numbers, there must be a comparison between each pair of adjacent elements in the
sorted order.
(b) Prove that the comparison tree has height height at least log2
(n!).
2. A mode of a sequence of numbers is a number that occurs the most times in the sequence.
Prove that the time complexity of determining a mode of a sequence of n numbers is in
Θ(n log n).
3. Suppose you are given two Boolean arrays A[1..n] and B[1..n] each of which is sorted (i.e. in
each array, all occurrences of 0 occur before all occurrences of 1). The problem is to determine
whether both arrays have the same number of occurrences of 1 and, if not, which array has
more occurrences.
(a) Prove that, when n = 1, both bits must be read in the worst case and, when n = 2, all
four bits must be read in the worst case.
(b) Determine the worst case probe complexity of this problem to within an additive constant
(i.e., for some function f(n), prove that any algorithm that solves this problem must
read at least f(n) bits in the worst case and give an algorithm solving this problem that
reads at most f(n) + O(1) bits).
If you cannot do this, you will get part marks for proving upper and lower bounds that
match to within a constant factor.
1
