In class, we learned a linear time algorithm that finds the median of an array o
ID: 3785897 • Letter: I
Question
In class, we learned a linear time algorithm that finds the median of an array of numbers. We now wish to solve a more general problem using this algorithm. The input is an (unsorted) array of numbers x_1, x_2, ..., x_n, each with an associated positive weight (we denote the weight of X_i by w_i) such that the sum of weights is 1 (i.e., sigma_i = 1^n w_i = 1). Suppose phi defines an ordering of indices such that x_phi(1), x_phi(2), , x_phi(n) is sorted. The weighted median of the numbers is the value X_phi(m) such that sigma_i = 1^m - 1w_phi(i)Explanation / Answer
Idea:
Assume an array a of n elements and you want to find the kth smallest element. First, do one linear scan in (n) times, which thus finds the min and max of the array. Now, suppose k n/2, we add n 2k copies of min 1 to the array. Else, add 2k n copies of max +1 to the array. In these two cases we get 2(nk) or 2k( respectively), as the new no. of elements. The previous kth element will now be at position k + (n 2k) = n k in the former case, and still same in position k in the latter case. Finally, the previous kth element will be the median of the new array. Therefore after this modification which took linear time , we can simply run the linear-time as a function call for finding the median, and it will return the right element.
Definition of Weighted Median:
“Weighted median of a set, partitions that set in two halves such that sum of weights in each partition is as equal as possible.”
If weights of all numbers in the set are equal then median is same as weighted median.
When set has even number of elements, we will have lower weighted median and upper weighted median instead of a single element as median.
Eg:-
Consider the set of numbers {0.1;0.35;0.05;0.1;0.15;0.05;0.2} .
Let each number have weights {0.1;0.35;0.05;0.1;0.15;0.05;0.2} respectively.
We get,
Median = 0.1 and
Weighted Median = 0.2
Algorithm
Usual algorithm takes O(nlog n) time when we sort and unsorted array. The algorithm below is reduced way:-
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.