You know two strategies for selecting k top-rank achievers (by GPA) in an unorde

Question

You know two strategies for selecting k top-rank achievers (by GPA) in an unordered list of GPA records for n university students: Run k times quickselect with linear processing time, T_qselect(n) = cn, in order to sequentially fetch the students of the rank n, n - 1, and so on up to n - k + 1, or Run once quicksort with linearithmic processing time, T_qsort(n) = cnlog_2n, to sort the entire list in ascending GPA order and fetch the k top-rank students. Let both the algorithms have the same factor c and let data fetching take negligibly small time, comparing to sorting. Find out. in terms of k and n, when Option 4a is faster than Option 4b, and determine, which option should be used if k = 10 and n = 32, 768 = 2^15.

Explanation / Answer

The selection problem is to find the kth largest element in an unsorted array.

Can solve in O(n log n) time by sorting and taking the kth largest element.

Partition-Based Selection

Recall: The median-of-medians algorithm belongs to a family of algorithms based on the partition algorithm:

Choose a pivot.

Use partition to place it correctly.

Stop if the pivot is in the right place.

Recurse on one piece of the array otherwise.

With no constraints on how the pivot is chosen, runtime is (n) and O(n 2 ). Can solve in O(n) time (with a large constant factor) using the “median-of-medians” algorithm.

We have

Since all i 's are independent (we make independent random choices at each level), this simplifies to

P() = P( i=1 to n i ) = i=1 to n P(i )

If i > 1, then P(i ) = 2 / i. P(1 ) = 1.

Thus P() = P( i=1 n i )

P() = i=1to n P(i ) = i=2 to n 2/ i = 2^n-1/n!

The probability of triggering the worst-case behavior of quickselect is

P() = 2^ n1/ n! given n=32 so substitute in the p()then we get

P() =2^32-1/32!=2^31/32.

Average case analysis

E[W ] cn k=0 to log4/3n E[ Xk ]( 3/ 4 ) k then substitute the given values we get

E[W ] value.

4b option should be used for k=10 and n=32.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.