We are given a set S of n elements so that the i-th element has value...

 

Transcribed Image Text:

We are given a set S of n elements so that the i-th element has value x; and weight wi. All weights are positive real numbers and the sum of all weights is 1, Σ²±1 Wi = 1. Let a Wi denote the total weight of all elements in S with values less than a. Let >a 2° a Wi denote the total weight of all elements in S with values greater than a. The weighted median of S is the element x satisfying Σ<* Wi < and > <½. For example, suppose that element values are 1, 2, 3, 5, 8, 10, 12 and element weights are 0.05, 0.05, 0.1, 0.1, 0.15, 0.2, 0.35 respectively. Then the weighted median is 10, but the median is the element with value 5. Your input consists of two unsorted arrays X [1..n] and W[1..n], where for each index i, the i-th element has value X [i] and weight W[i]. You may assume that all values are distinct. a) Explain how we can compute the weighted median in O(nlogn) time using sorting. b) Describe an algorithm that computes the weighted median in O(n) time using the linear-time selection algorithm as a subroutine. We are given a set S of n elements so that the i-th element has value x; and weight wi. All weights are positive real numbers and the sum of all weights is 1, Σ²±1 Wi = 1. Let a Wi denote the total weight of all elements in S with values less than a. Let >a 2° a Wi denote the total weight of all elements in S with values greater than a. The weighted median of S is the element x satisfying Σ<* Wi < and > <½. For example, suppose that element values are 1, 2, 3, 5, 8, 10, 12 and element weights are 0.05, 0.05, 0.1, 0.1, 0.15, 0.2, 0.35 respectively. Then the weighted median is 10, but the median is the element with value 5. Your input consists of two unsorted arrays X [1..n] and W[1..n], where for each index i, the i-th element has value X [i] and weight W[i]. You may assume that all values are distinct. a) Explain how we can compute the weighted median in O(nlogn) time using sorting. b) Describe an algorithm that computes the weighted median in O(n) time using the linear-time selection algorithm as a subroutine.

Answer rating: 100% (QA)

a To compute the weighted median in Onlogn time using sorting we can follow these steps 1 Combine th... View the full answer