Also, proof of correctness.

Problem 3. You are given a collection of n integers a1,..., An with positive weights W1, ..., Wn. For any number ai, we define the bias of a; as: bias(ai) = w; wklj j:ajai k:akai i.e., the absolute value of the difference between the weights of elements smaller than di 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 ai = A[i] and wi = W[i]. Examples: When n= 5, and A = (1,5, 3, 2, 7] and W [3, 6, 2,8, 9), the smallest biased element is a2 = A[2] = 5 with bias(az) = |(3+2+8) (6 +9)| 2. 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. (a) Algorithm: (7 points) Problem 3. You are given a collection of n integers a1,..., An with positive weights W1, ..., Wn. For any number ai, we define the bias of a; as: bias(ai) = w; wklj j:ajai k:akai i.e., the absolute value of the difference between the weights of elements smaller than di 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 ai = A[i] and wi = W[i]. Examples: When n= 5, and A = (1,5, 3, 2, 7] and W [3, 6, 2,8, 9), the smallest biased element is a2 = A[2] = 5 with bias(az) = |(3+2+8) (6 +9)| 2. 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. (a) Algorithm: (7 points)