1. Write a routine to reconstruct the shortest paths from the algorithm in Section 10.3.4.

2. The binomial coef?cients C(N, k) can be de?ned recursively as follows: C(N, 0) = 1, C(N, N) = 1, and, for 0 <>k <>N, C(N, k) = C(N - 1, k) + C(N - 1, k - 1). Write a function and give an analysis of the running time to compute the binomial coef?cients as follows:

a. recursively

b. using dynamic programming

3. Write the routines to perform insertion, deletion, and searching in skip lists.

4. Give a formal proof that the expected time for the skip list operations is O(log N).

5. a. Examine the random-number generator on your system. How random is it?

b. Figure 10.75 shows a routine to ?ip a coin, assuming that random returns an integer (which is prevalent in many systems). What is the expected performance of the skip list algorithms if the random-number generator uses a modulus of the form M = 2B(which is unfortunately prevalent on many systems)?