1. Suppose we are given a set S of n items, each with a value and a weight. For
ID: 3071030 • Letter: 1
Question
1. Suppose we are given a set S of n items, each with a value and a weight. For any element x ES, we define two subsets ·Sex is the set of all elements of S whose value is smaller than the value of x. ·S× is the set of all elements of S whose value is larger 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 any element x such that w(Scx) S w(S)/2 and w(S^x)S w(S)/2. Describe and analyze an algorithm to compute the weighted median of a given weighted for each index i, the ith element has value S[i] and weight W[i]. You may assume that all values are distinct and all weights are positive.Explanation / Answer
ANS::
as per given data
//Given two unsorted array, A and W
STEP 1: Find W(S)/2 by traversing the W array in O(N)
STEP 2: Find Median of Array A, say mx using Selection algorithm, since this is unsorted array
STEP 3: Find weight of each partition, if sum of left partition< 1/2 W(s) and weight of right partition < 1/2 W(s), then this is weighted mean
STEP 4: Find above condition do not hold, add one more element and recursively do the step 3 to get the weighted median
//How to get median of unsorted array in O(N)
We can use Quick sort partition algorithm by taking the last element as pivot
(https://cs.stackexchange.com/questions/56299/find-a-weighted-median-for-unsorted-array-in-linear-time)
if you have any doubts pls comments below
pls rate thumbs up
thank you
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.