Computer Science 673 Homework 4: Medians & Trees Q1 2 3 Solution

Question: #8936

Computer Science 673 Fall 2015
Homework 4: Medians & Trees

All problem / exercise numbers are from the 3nd edition of Introduction to Algorithms
(the 1st and 2nd editions are di erent!) Note the di erence between problems and exercises!

1. Special Cases of Select:
(a) (4 points) Give an algorithm to nd the second smallest element in a list of n elements in at most n + dlg ne 􀀀 2 comparisons. Note: Your algorithm can use no more than n + dlg ne 􀀀 2 total comparisons in the worst case. Hint: Find the smallest element, too.

(b) (4 points) Give an algorithm to nd the 3rd smallest element in a list, using the smallest number of worst-case comparisons. Exactly how many comparisons does your algorithm take in the worst case? Hint: Use your solution to part a | you will need to nd the smallest and second-smallest element as well!

2. Exercise 9.3-6 quantiles The kth quantiles of an n-element set ar the k􀀀1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the
k-th quantiles of a set. Elements within each quantitle can be listed in any order. 3. (5 points) Exercise 9.3-8 Finding the median of two lists of numbers Let X[1 : : : n] and Y [1 : : : n] be two arrays, each containing n elemetns already in sorted order. Give an O(lg n)-time algorithm to nd the median of all 2n elements in arrays X and Y .

Solution: #8964

Computer Science 673 Homework 4: Medians & Trees Q1 2 3 Solution

if a2k>a2k+1, interchange them. On the second pass compare a4k with a4k+2 for 0≤k<(n−2)/4; if a4k>a4k+2, interchange the pair ⟨a4k,a4k+1⟩ with the pair ⟨a4k+2,a4k+3⟩. On the i-th pass compare a2ik with a2ik+2i−1 for 0≤i<(n−2i−1)/2i; if a2ik>a2ik+2i−1, interchange the...