Just as with ordinary serial algorithms, we sometimes want to implement randomized multithreaded algorithms. This problem explores

Question:

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 TP, T1, and T∞ are all random variables.

b. Consider a randomized multithreaded algorithm for which 1% of the time we have T1 = 104 and T10,000 = 1, but for 99% of the time we have T1 = T10,000 = 109. Argue that the speedup of a randomized multithreaded algorithm should be defined as E [T1] =E [TP], rather than E O[1/TP].

c. Argue that the parallelism of a randomized multithreaded algorithm should be defined as the ratio E [T1] =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.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Posted: