# Question

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|.

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|.

## Answer to relevant Questions

The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notation is rather large. When i is small ...Suppose that we wish to keep track of a point of maximum overlap in a set of intervals—a point that has the largest number of intervals in the database overlapping it.a. Show that there will always be a point of maximum ...The off-line minimum problem asks us to maintain a dynamic set T of elements from the domain {1, 2, ..., n} under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m EXTRACT-MIN calls, where ...Given an m × n matrix T over some field (such as the reals), show that (S,ℓ) is a matroid, where S is the set of columns of T and A ¬ℓ if and only if the columns in A are linearly independent.Consider an ordinary binary min-heap data structure with n elements that supports the instructions INSERT and EXTRACT-MIN in O (lg n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT ...Post your question

0