Description
1. [8 marks] Suppose you have the elements 1, …,10 stored in that order in a list.
(a) How many elements inspections occur in performing the following sequence of
searches: 3, 10, 3, 4, 5, 3, 5, 9, 8, 3.
(b) Find the static ordering of the list that minimizes the number of comparisons to
perform this sequence of requests for the above sequence. How many
comparisons does it use?
(c) Give a request sequence in which the move to front heuristic does better than the
static optimal for the proposed sequence of requests. Justify this claim.
2. [8 marks] In class, we discussed a “doubling binary search” technique for finding the
“min-max” approximation to the optimal binary search tree, and claimed that it ran in
O(n) time even though it involved up to n “binary searches”. The key point was that
the search for the root of a given subrange took O(1 + lg(v)) time, where v is the
position of the root relative to the subrange. (i.e. The root is the vth node from the left
or right, whichever is less). Prove the method takes O(n) time. To do so you may
choose do it in the following two parts.
a) To simplify things, first assume that an individual search takes Ceiling(lg v)
steps, and show that the cost of determining the entire tree is O(n) (i.e. the
amortized cost of a search is O(1)) [Hint: It is probably easiest to show an
explicit constant, c, such that the runtime is less than cn]
b) Complete the proof by using part a) to show that the entire process takes O(n)
time even if the individual search takes p + q Ceiling(lg v) time (for positive
constants p and q.
