want a clearly explanation thank u soooo much 3. (20 points) Let a1,---, an be n
ID: 3589937 • Letter: W
Question
want a clearly explanation thank u soooo much
3. (20 points) Let a1,---, an be n distinct real numbers, and wi, .., wn be a set of n positive weights with wit . . . + wn-1. The weighted median of the set { 1, . . . ,, } is the number k Give a (n) worst-case running time algorithm computing the weighted median. an O(n2)-time algorithm to determine whether there exist three distinct numbers ai, aj and a) Prove that such an ak always existsS 4. (15 points) Given a set S {al, . . . , an} of n unsorted real numbers and a real value B, design ak in S such that ai +aj +ak- B.Explanation / Answer
3a) Lets sort the numbers a1..an and their weights in the increasing order of numbers. let w1..wn be the weights in new sorted order, then w1+w2+...+wn =1 and there always exists a k where w1+w2+...+wk >=1/2 and w1+w2+..wk-1<1/2 since all weights are positive. And wk+1+...+wn <=1/2, So there always exists a ak which is a weighted median.
3b) We can use modified version of selection algorithm that can find a median in linear time. In partition phase of the algorithm we also partitions weights with the elements and once the partition is done we compute the sum of weights in one partition to know in which partition the weighted median is present. if we get the sum >1/2 then we need to find the medin in that partion else we need to continue with the other partition. This variant will give us the weighted median and it runs in same linear time.
4)
1) Sort the elements in increasing order.
2) Fix the first element as A[i] where i is from 0 to array size – 2. After fixing the first element of triplet, find the other two elements using method below
3) Let remaining = B - A[i]
Method
---------------
Time complexity
---------------------------
Sorting takes O(nlogn). The method takes O(n) time and it called atmost n-2 times for each time fixing the first element . so total time is O(n2) .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.