Exercise 10.3-4 asked how we might maintain an n-element list compactly in the first n positions of
Question:
Exercise 10.3-4 asked how we might maintain an n-element list compactly in the first n positions of an array. We shall assume that all keys are distinct and that the compact list is also sorted, that is, key[i]
COMPACT-LIST-SEARCH (L, n, k)
If we ignore lines 3-7 of the procedure, we have an ordinary algorithm for searching a sorted linked list, in which index i points to each position of the list in turn. The search terminates once the index i "falls off" the end of the list or once key[i ] ≥ k. In the latter case, if key[i] = k, clearly we have found a key with the value k. If, however, key[i] > k, then we will never find a key with the value k, and so terminating the search was the right thing to do.
Lines 3-7 attempt to skip ahead to a randomly chosen position j. Such a skip benefits us if key[j] is larger than key[i] and no larger than k; in such a case, j marks a position in the list that i would have to reach during an ordinary list search.
Because the list is compact, we know that any choice of j between 1 and n indexes some object in the list rather than a slot on the free list.
Instead of analyzing the performance of COMPACT-LIST-SEARCH directly, we shall analyze a related algorithm, COMPACT-LIST-SEARCH′, which executes two separate loops. This algorithm takes an additional parameter t which determines an upper bound on the number of iterations of the first loop.
COMPACT-LIST-SEARCH′ (L, n, k, t)
To compare the execution of the algorithms COMPACT-LIST-SEARCH (L, n, k) and COMPACT-LIST-SEARCH′ (L, n, k, t), assume that the sequence of integers returned by the calls of RANDOM (1, n) is the same for both algorithms.
a. Suppose that COMPACT-LIST-SEARCH (L, n, k) takes t iterations of the while loop of lines 2-8. Argue that COMPACT-LIST-SEARCH′ (L, n, k, t) returns the same answer and that the total number of iterations of both the for and while loops within COMPACT-LIST-SEARCH′ is at least t .
In the call COMPACT-LIST-SEARCH′ (L, n, k, t), let Xt be the random variable that describes the distance in the linked list (that is, through the chain of next pointers) from position i to the desired key k after t iterations of the for loop of lines 2-7 have occurred.
b. Argue that the expected running time of COMPACT-LIST-SEARCH′ (L, n, k, t) is O(t + E [Xt]).
c. Show that E
d. Show that
e. Prove that
f. Show that COMPACT-LIST-SEARCH′ (L, n, k, t) runs in O(t + n/t) expected time.
g. Conclude that COMPACT-LIST-SEARCH runs in O(√n) expected time.
h. Why do we assume that all keys are distinct in COMPACT-LIST-SEARCH? Argue that random skips do not necessarily help asymptotically when the list contains repeated key values.
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest