Suppose we are given a set S of n items, each with a distinct value and a positive weight. For any element x S, we define two subsets

S < x is the set of elements of S whose value is strictly less than the value of x.

S > x is the set of elements of S whose value is strictly more than the value of x.

For any subset R S, let w(R) denote the sum of the weights of elements in R. The weighted median of R is the unique element x such that w(Sx ) > w(S)/2. In other words, if we were to sort the elements of S by value and then add up their weights one-by-one in order, the first element to take our sum strictly beyond half the total weight of S is the weighted median.

Describe and analyze an algorithm to compute the weighted median of a given weighted set in O(n) time. Input consists of two unsorted arrays S[1 .. n] and W[1 .. n], where for each index i, the ith element has value S[i] and weight W[i].

If it is helpful, feel free to call the O(n)time procedures MomSelect(A[1 .. n], k) and Partition(A[1 .. n], p) as defined in class. We can also assume any changes to S[1 .. n] are accompanied by identical changes to W[1 .. n] so that at all times and for any index i, value S[i] and weight W[i] both refer to the same weighted element.

Advice: Might modify QuickSelect so 1) are guaranteed to use the median as the pivot and 2) recursively search the correct subarray to find the weighted median of the input set. Be careful when specifying which element are looking for in the recursive call.