[Algo] Problem 9

Problem 9-1 Largest i numbers in sorted order
Given a set of n numbers, we wish to find the i largest in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of n and i.
a. Sort the numbers, and list the i largest.
b. Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.
c. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers.
solution:
a. Sort the numbers by heapsort $\Rightarrow \Theta(n\lg n)$
List the i largest $\Rightarrow \Theta(i)$
Total: $\Theta(n\lg n) + \Theta(i) = \Theta(n\lg n)$

b. Build a max-priority queue $\Rightarrow$ call MAX-HEAP-INSERT n times $\Rightarrow O(n\lg n)$
Call EXTRACT-MAX i times $\Rightarrow i\times O(\lg n) = O(i\lg n)$
Total: $O(n\lg n) + O(i\lg n) = O(n\lg n)$

c. Find the ith largest number  $\Rightarrow O(n)$
Partition around the number $\Rightarrow O(n)$
Sort the i largest numbers $\Rightarrow O(i\lg i)$
Total: $O(n + i\lg i)$


Problem 9-2 Weighted median
For n distinct elements $x_1, x_2, \ldots, x_n$ with positive weights $w_1, w_2, \ldots, w_n$ such that $\sum_{i=1}^n w_i = 1$, the weighted (lower) median is the element $x_k$ satisfying $$\sum_{x_i < x_k}w_i < \frac{1}{2}$$ and $$\sum_{x_i > x_k}w_i \leq \frac{1}{2}.$$
a. Argue that the median of $x_1, x_2, \ldots, x_n$ is the weighted median of the $x_i$ with weights $w_i = 1/n$ for $i = 1, 2, \ldots, 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 $\Theta(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 $p_1, p_2, \ldots, p_n$ with associated weights $w_1, w_2, \ldots, w_n$. We wish to find a point p (not necessarily one of the input points) that minimizes the sum $\sum_{i=1}^n w_id(p, p_i)$ 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 = (x_1, y_1)$ and $b = (x_2, y_2)$ is the Manhattan distance given by $d(a, b) = |x_1 - x_2| + |y_1 - y_2|$.

solution:
a. Let $y_1, y_2, \ldots, y_n$ be the sorted list of $x_1, x_2, \ldots, x_n$. The median is therefore $y_k$, where $k = \lfloor (n+1)/2 \rfloor$. In that case,
$$\sum_{y_i < y_k}\frac{1}{n} \leq \sum_{i=1}^{\lfloor (n+1)/2 \rfloor - 1}\frac{1}{n} = \frac{\lfloor (n+1)/2 \rfloor - 1}{n} < \frac{n-1}{2n} < \frac{1}{2},$$ and
$$\sum_{y_i > y_k}\frac{1}{n} \leq \sum_{i=\lfloor (n+1)/2 \rfloor + 1}^{n}\frac{1}{n} = \frac{n - \lfloor (n+1)/2 \rfloor}{n} \leq \frac{n - n/2}{n} = \frac{1}{2}.$$
Hence, $y_k$ is the weighted median as well.

b. We can sort $x_1, x_2, \ldots, x_n$ to get the sorted list $y_1, y_2, \ldots, y_n$. And find the weighted median by summing up the weights from $w_1$. Sorting whole list takes $O(n\lg n)$ time, and finding the weighted median according to the sorted list takes $O(n)$ time. So, total time is $O(n\lg n)$.

c.
@{
\proc{Weighted-Mediam}(X)
\li n = |X|
\li \If n = 1
\li \;\;\;\;\Return X[1]
\li \Elif |X| = 2
\li \;\;\;\;\Return\textup{max}(X[1], X[2])
\li \Else
\li \;\;\;\;x_k = \proc{Select}(X, 1, n, \lfloor(n+1)/2\rfloor)
\li \;\;\;\;L = \Sigma_{x_i < x_k} w_i
\li \;\;\;\;R = \Sigma_{x_i > x_k} w_i
\li \;\;\;\;\If L < 1/2 \;\textup{and}\; R \leq 1/2
\li \;\;\;\;\;\;\;\;\Return x_k
\li \;\;\;\;\Elif L \geq 1/2
\li \;\;\;\;\;\;\;\;w_k = w_k + R
\li \;\;\;\;\;\;\;\;X^{'} = \{x | x \in X \textup{and} x \leq x_k\}
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;w_k = w_k + L
\li \;\;\;\;\;\;\;\;X^{'} = \{x | x \in X \textup{and} x \geq x_k\}
\li \;\;\;\;\Return \proc{Weighted-Median}(X^{'})
}@