For n distinct elements x1, x2, ..., xn with positive weights w1, w2, ..., wn such that Σni =1 wi = 1, the weighted (lower) median is the element xk satisfying



a. Argue that the median of x1, x2, ..., xn is the weighted median of the xi with weights wi = 1/n for i = 1,2, ..., n.
b. Show how to compute the weighted median of n elements in O (n lg n) worst-case time using sorting.
c. Show how to compute the weighted median in Θ (n) worst-case time using a linear time median algorithm such as SELECT from Section 9.3.
The post-office location problem is defined as follows. We are given n points p1, p2, ..., pn with associated weights w1, w2, ..., wn. We wish to find a point p (not necessarily one of the input points) that minimizes the sum, where d(a, b) is the distance between points a and b.
d. Argue that the weighted median is a best solution for the 1-dimensional post-office location problem, in which points are simply real numbers and the distance between points a and b is d(a, b) = |a - b|.
e. Find the best solution for the 2-dimensional post-office location problem, in which the points are (x, y) coordinate pairs and the distance between points a = (x1, y1) and b = (x2, y2) is the Manhattan distance given by d (a, b) = |x1 - x2| + |y1 - y2|.

". 4S and