Just as with ordinary serial algorithms, we sometimes want to implement randomized multithreaded algorithms. This problem explores how to adapt the various performance measures in order to handle the expected behavior of such algorithms. It also asks you to design and analyze a multithreaded algorithm for randomized quicksort.

a. Explain how to modify the work law (27.2), span law (27.3), and greedy scheduler bound (27.4) to work with expectations when T_P, T₁, and T∞ are all random variables.

b. Consider a randomized multithreaded algorithm for which 1% of the time we have T₁ = 10⁴ and T_10,000 = 1, but for 99% of the time we have T₁ = T_10,000 = 10⁹. Argue that the speedup of a randomized multithreaded algorithm should be defined as E [T₁] =E [T_P], rather than E O[1/T_P].

c. Argue that the parallelism of a randomized multithreaded algorithm should be defined as the ratio E [T₁] =E [T∞].

d. Multithread the RANDOMIZED-QUICK-SORT algorithm on page 179 by using nested parallelism. (Do not parallelize RANDOMIZED-PARTITION.) Give the pseudocode for your P-RANDOMIZED-QUICK-SORT algorithm.

e. Analyze your multithreaded algorithm for randomized quicksort.