You are given a collection of n integers a,..., an with positive weights w,..., wn. For...

Transcribed Image Text:

You are given a collection of n integers a₁,..., an with positive weights w₁,..., wn. For any number a;, we define the bias of a; as: Examples: i.e., the absolute value of the difference between the weights of elements smaller than a; and the remaining ones. Design and analyze an algorithm that in O(n log n) time finds the element that has the smallest bias. You can assume that the input is given in two arrays A[1: n] and W[1: n] where a; = A[i] and w; = W[i]. bing(a;) = Ι Σ w; - j:a, <a (a) Algorithm: Σ wal; • When n = 5, and A = [1,5,3,2,7] and W = [3, 6, 2, 8, 9], the smallest biased element is a₂ = A[2] = 5 with bias(a2) |(3+2+8) (6+9) = 2. (b) Proof of Correctness: kaza • When n = 5, and A = [1,2,3, 4, 5] and W = [8, 6, 5, 2, 6], the smallest biased element is a3 = A[3] = 3 with bias(a3)= |(8+6) - (5+2 +6) = 1. (c) Runtime Analysis: You are given a collection of n integers a₁,..., an with positive weights w₁,..., wn. For any number a;, we define the bias of a; as: Examples: i.e., the absolute value of the difference between the weights of elements smaller than a; and the remaining ones. Design and analyze an algorithm that in O(n log n) time finds the element that has the smallest bias. You can assume that the input is given in two arrays A[1: n] and W[1: n] where a; = A[i] and w; = W[i]. bing(a;) = Ι Σ w; - j:a, <a (a) Algorithm: Σ wal; • When n = 5, and A = [1,5,3,2,7] and W = [3, 6, 2, 8, 9], the smallest biased element is a₂ = A[2] = 5 with bias(a2) |(3+2+8) (6+9) = 2. (b) Proof of Correctness: kaza • When n = 5, and A = [1,2,3, 4, 5] and W = [8, 6, 5, 2, 6], the smallest biased element is a3 = A[3] = 3 with bias(a3)= |(8+6) - (5+2 +6) = 1. (c) Runtime Analysis: