2010年12月29日 星期三

[Algo] Exercise 9.3

Exercise 9.3-1
In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.
solution:
(1) groups of 7 are used
# of elements greater than the median of median is at least
$$4(\lceil\frac{1}{2}\lceil\frac{n}{7}\rceil\rceil - 2) \geq \frac{2n}{7} - 8$$.
The recurrence can be rewritten as
$$T(n) \leq T(\lceil\frac{n}{7}\rceil) + T(\frac{5n}{7} + 8) + O(n)$$.
The process of proving is similar to the textbook, and we will prove that $T(n) = O(n)$ finally.

(2) groups of 3 are used
# of elements greater than the median of median is at least
$$2(\lceil\frac{1}{2}\lceil\frac{n}{3}\rceil\rceil - 2) \geq \frac{n}{3} - 4$$.
The recurrence can be rewritten as
$$T(n) \leq T(\lceil\frac{n}{3}\rceil) + T(\frac{2n}{3} + 4) + O(n)$$.
Before we derive the following steps, we can glance at the equation and find out the right hand side $n/3 + 2n/3 + 4 \geq n$. Suppose that $T(n) \leq cn$ for some positive constant c.  By substitution, we have

Since $5c + an \geq 0$, we cannot derive that $T(n) \leq cn$. Hence, SELECT does not run in linear time if groups of 3 are used.


Exercise 9.3-2
Analyze SELECT to show that if $n \geq 140$, then at least $\lceil n/4 \rceil$ elements are greater than the median-of-medians x and at least $\lceil n/4 \rceil$ elements are less than x.
solution:
Suppose that at most $\lceil n/4 \rceil$  elements are greater than x, then we can obtain that
$$\lceil n/4 \rceil \geq \frac{3n}{10} - 6 \Rightarrow \frac{n}{4} + 1 > \frac{3n}{10} - 6 \Rightarrow n < 140$$.
It contradicts $n \geq 140$! Hence, we can prove that if $n \geq 140$, then at least $\lceil n/4 \rceil$ elements are greater than the median-of-medians x and at least $\lceil n/4 \rceil$ elements are less than x.


Exercise 9.3-3
Show how quicksort can be made to run in $O(n\lg n)$ time in the worst case, assuming that all elements are distinct.
solution:
Before PARTITION is performed, we call SELECT to pick up the median of the input array. The median is used for a pivot to split the array into two subarrays. Because of the median, it guarantees the left hand side and right hand side must be of the same length. Let $T(n)$ be the running time needed by the modified quicksort to perform on input array of n elements. We can derive the recurrence as follows: $T(n) \leq 2T(n/2) + \Theta(n)$. By master theorem, $T(n) = \Theta(n\lg n)$.

MODIFIED-PARTITION(A, p, r)
n = r - p + 1
find an index k by calling SELECT(A, p, r, $\lfloor(n+1)/2\rfloor$) such that A[k] = x, where x is the median
3  exchange A[r] and A[k]
4  return PARTITION(A, p, r)



Exercise 9.3-4
Suppose that an algorithm uses only comparisons to find the ith smallest element in a set of n elements. Show that it can also find the i -1 smaller elements and n - i larger elements without performing any additional comparisons.
solution:
Suppose that the algorithm uses m comparisons to find the ith smallest element x in a set of n elements. If we trace these m comparisons in the log, we can easily find the i -1 smaller elements by transitivity. If x > a and a > b, then x > b can be deduced without actually performing a comparison between x and b. Similarly, the n - i larger elements can be found, too. Is it possible there exists a number, say p, we cannot decide whether x is greater than p or not by the comparison log? That's impossible! Otherwise, the algorithm does not work correctly.


Exercise 9.3-5
Suppose that you have a "black-box" worst-case linear-time median subroutine. Give a simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.
solution:
MODIFIED-SELECT(A, p, r, i)
1  if p == r
2    return A[p]
3  x = MEDIAN(A, p, r)
4  q = PARTITION'(A, p, r, x)
5  k = q - p + 1
6  if i == k
7    return A[q]
8  else if i < k
9    return MODIFIED-SELECT(A, p, q-1, i)
10 else
11   return MODIFIED-SELECT(A, q+1, r, i-k)

PARTITION' is a deterministic PARTITION subroutine. It uses parameter x as a pivot to split the array. Since the median is found to split the array, the subarrays will be of the same size. $$T(n) \leq T(n/2) + O(n) \Rightarrow T(n) = O(n)$$.


Exercise 9.3-6
The kth quantiles of an n-element set are the k-1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an $O(n\lg k)$-time algorithm to list the kth quantiles of a set.
solution:
The k quantiles of an n-element array A are
$A[\lceil 1\cdot n/k \rceil], A[\lceil 2\cdot n/k \rceil],\cdots,A[\lceil (k-1)\cdot n/k \rceil]$.
The following algorithm finds kth quantiles of an array A, and these (k-1) elements are put  just like the positions they reside if entire range is sorted.

QUANTILE-BASE(A, p, r, Q, k)
1  if k <= 0
2    return
3  else if k == 1
4    x = SELECT(A, p, r, Q[1])
5    PARTITION(A, p, r, x)
6  else
7    i = $\lfloor (k + 1)/2 \rfloor$
8    x = SELECT(A, p, r, Q[i])
9    q = PARTITION(A, p, r, x)
10   QUANTILE-BASE(A, p, q - 1, Q[1..(i-1)], i - 1)
11   for j = (i + 1) to length[Q]
12     Q[j] = Q[j] - Q[i]
13   QUANTILE-BASE(A, q + 1, r, Q[(i+1)..length[Q]], k - i)

QUANTILE(A, p, r, k)
1  if k <= 1
2    return
3  n = r - p + 1
4  QUANTILE-BASE(A, p, r, $[\lceil 1\cdot n/k \rceil, \lceil 2\cdot n/k \rceil,\cdots,\lceil (k-1)\cdot n/k \rceil]$, k - 1)

Next, we prove the running time is $O(n\lg k)$. Let $T(n, k)$ be the running time of the algorithm needs to find k-quantiles of an n-element array. We have,


Have no energy to draw the recursion tree to illustrate the complexity. Maybe tomorrow...


Exercise 9.3-7
Describe an $O(n)$-time algorithm that, given a set S of n distinct numbers and a positive integer $k \leq n$, determines the k numbers in S that are closest to the median of S.
solution:
The median x can be found by the procedure SELECT in $O(n)$ time. After finding the median x, we call the a modified procedure SELECT' to find the kth element. In the modified procedure SELECT', the elements, for instance $a, b$ are compared by the distance to the median x($$|a-x| - |b-x|$$). The comparison takes $\Theta(1)$ time. So the modified SELECT' still runs in $O(n)$ time. After the kth element is found by SELECT', it is used as the pivot to partition the set S, and S[1..k] is the k numbers that are closeset to the median.


Exercise 9.3-8
Let $X[1..n]$ and $Y[1..n]$ be two arrays, each containing n numbers already in sorted order. Give an $O(\lg n)$-time algorithm to find the median of all 2n elements in array X and Y.
solution:
Let Z be the union of array X and array Y and in sorted order. The median m of Z is the nth order statistics, that is, m must be greater than exactly (n-1) numbers. Suppose that m is in the array X, then we can claim that there must exist an index p such that $X[p] = m$ and $Y[n-p] \leq X[p] \leq Y[n-p+1]$. Why? X[p] is greater than exactly p-1 numbers in X. And $Y[n-p] \leq X[p] \leq Y[n-p+1]$, then X[p] is greater than exactly n-p numbers in Y. Thus, X[p] is greater than exactly n-1 numbers in total and X[p] must be the median m.
The following algorithm can help us find the median m. It tries to find the median in X first. If it fails, the median must be in Y. The procedure then tries to find the median in Y. Since the median must be either in X or Y. The procedure would not be called infinitely.
FIND-MEDIAN(X, Y, start_index, end_index, n)
1  if start_index > end_index
2    return FIND-MEDIAN(Y, X, 1, n, n)
3  p = (start_index + end_index)/2
4  a = X[p]
5  if a >= Y[n - p] and a <= Y[n - p + 1]
6    return X[p]
7  else if a < Y[n - p]
8    return FIND-MEDIAN(X, Y, p+1, end_index, n)
9  else
10   return FIND-MEDIAN(X, Y, start_index, p-1, n)

Then, we are going to show that the algorithm needs $O(\lg n)$ time. Each time the procedure is called, the distance between start_index and end_index is divided by 2. If the median is in X, the running time is at most $O(\lg n)$. Otherwise, it continues to search into Y, and the running time is $O(\lg n) + O(\lg n) = O(\lg n)$.


Exercise 9.3-9
Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. From each well, a spur pipeline is to be connected directly to the main pipeline along a shortest path (either north or south), as shown in Figure 9.2. Given x- and y-coordinates of the wells, how should the professor pick the optimal location of the main pipeline (the one that minimizes the total length of the spurs)? Show that the optimal location can be determined in linear time.
solution:
Let $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$ be the coordinates of n wells. We want to find a number $y^*$ such that $$d(y^*) = \sum_{i = 1}^n |y_i - y^*|$$ achieves the minimum. Note that $$|y_i - y^*|$$ is the distance between $y_i$ and $y^*$. The median of $y_1, y_2, \ldots, y_n$ will always have less value than any other fixed number substituted into function $d(\cdot)$. So the optimal location can be determined by SELECT in $O(n)$ time.

[Algo] 9.3 Selection in worst-case linear time

SELECT 的原理
這一個 section 要提出另一個演算法叫作 SELECT,它的時間複雜度也是 $O(n)$,不過它跟 RANDOMIZED-SELECT 最大的不同就是它保證每次的 partition 都是好的 split。
假設 input array 的長度是 n(n > 1),如果長度為1的話,那 SELECT 會回傳它唯一的那個元素,這也是 recursive call 終結的條件。
1.  把這個 array 每 5 個 elements 就分成一個 group,所以會有 $\lfloor n/5 \rfloor$ 個長度為 5 的 groups,然後剩下不足 5 的 elements 就自己獨立成一個 group。
2. 各組分開作 insertion sort,然後把各組的 median 取出來變成一個 array。
3. 把這個 median 的 array,call 一次 SELECT,找出這個 array 的 median。我們把這個"median 的 median"叫作 x
4. 以 x 當作 pivot,把整個 input array 跑過一次 PARTITION,分成左右兩邊,假設左邊有 k - 1 個 elements,中間是 pivot x,那麼右邊就應該會有 n - k 個 elements。
5. 如果要找 ith order statistic 剛好是 pivot x 的話,那就回傳 x,否則我們看這個 order statistic 是落在右邊還是左邊,我們就 call SELECT 下去找。(當然啦,如果在右邊的話,就要找 (i - k)th order statistic)


SELECT 的時間複雜度

















如上圖,每個 element 都表示成一個點,每一個 column 就代表一個 group,白色的點是該 group 的 median,標示成 x 的就是 median 的 median。因為我們假設每個 element 都是相異的,所以至少有一半以上的 median 都會比 x 還要來的大。除了 x 自己這個 group 和最後一個 group 之外,其他每個 group 都會有 3 個 elements 比 x 還要大,所以我們可以得到:至少有
$$3(\lceil\frac{1}{2}\lceil\frac{n}{5}\rceil\rceil - 2) \geq \frac{3n}{10} - 6$$
個 elements 比 x 大,同理,有 $$\frac{3n}{10} - 6$$ 個 elements 比 x 小。因此,SELECT 在第 5 個步驟的 recursive call 最多只有 $$\frac{7n}{10} + 6$$ 個 elements 而已。
令 $T(n)$ 為 SELECT 跑在 array 長度為 n 時所需要的時間,並且假設 $T(n)$ 是遞增的。
第一步需要 $O(n)$ 的時間,
第二步需要 $O(n)$ 的時間(不用懷疑,5 個 elements 的 insertion sort 我們可以視為 $O(1)$),
第三步需要 $T(\lceil n/5 \rceil)$ 的時間,
第四步需要 $O(n)$ 的時間,
第五步最多需要 $T(7n/10 + 6)$ 的時間,
於是我們可以整理出如下的遞迴式:

看到上面的 140 了嗎?這個神奇的數字怎麼來的呢?慢慢來。
還是利用 substitution method,假設 $T(n) \leq cn$,$O(n) \leq an$,其中 a, c 各為一個常數。接著代進去原來的式子中:

只要 $-cn/10 + 7c + an \leq 0$,$T(n)$ 最多就是 $cn$ 而已。所以 $c \geq 10a(n/(n-70))$ 只要在 $n \geq 70$的情況下都會滿足,而且因為我們假設 $n \geq 140$,我們會得到 $n/(n-70) \leq 2$,所以只要 $c \geq 20a$ 的話,$-cn/10 + 7c + an$ 就會小於等於 0。所以其實 140 這個數字並不是那麼的神奇,我們可以任意指定它為一個大於 70 的數字,然後再為此挑一個適當的 c 就可以了。因此我們得證 SELECT 是 $O(n)$ 的演算法。

2010年12月28日 星期二

[Algo] Exercise 9.2

Exercise 9.2-1
Show that in RANDOMIZED-SELECT, no recursive call is ever made to a 0-length array.
solution:
When a 0-length array is made by partition, k must be either 1 or n. Recursive call will not be  made to a 0-length array unless we want 0-order statistic or (n+1)th order statistic.


Exercise 9.2-2
Argue that the indicator random variable $X_k$ and the value $T(\max(k-1, n-k))$ are independent.
solution:
Trivial. Occurrence of $X_k$ makes the time it takes to do the recursive call neither more nor less.


Exercise 9.2-3
Write an iterative version of RANDOMIZED-SELECT.
solution:
ITERATIVE-RANDOMIZED-SELECT(A, p, r, i)
while true
2    q = RANDOMIZED-PARTITION(A, p, r)
3    k = q - p + 1
4    if i == k
5      then return A[q]
6    else if i < k
7      then r = q - 1
8    else
9      p = q + 1
10     i = i - k


Exercise 9.2-4
Suppose we use RANDOMIZED-SELECT to select the minimum element of the array $A = \langle 3, 2, 9, 0, 7, 5, 4, 8, 6, 1\rangle$. Describe a sequence of partitions that results in a worst-case performance of RANDOMIZED-SELECT.
solution:
[3, 2, 9, 0, 7, 5, 4, 8, 6, 1]  --> [3, 2, 0, 7, 5, 4, 8, 6, 1] + [9]
[3, 2, 0, 7, 5, 4, 8, 6, 1] --> [3, 2, 0, 7, 5, 4, 6, 1] + [8]
[3, 2, 0, 7, 5, 4, 6, 1] --> [3, 2, 0, 5, 4, 6, 1] + [7]
[3, 2, 0, 5, 4, 6, 1] --> [3, 2, 0, 5, 4, 1] + [6]
[3, 2, 0, 5, 4, 1] --> [3, 2, 0, 4, 1] + [5]
[3, 2, 0, 4, 1] --> [3, 2, 0, 1] + [4]
[3, 2, 0, 1] --> [2, 0, 1] + [3]
[2, 0, 1] --> [0, 1] + [2]
[0, 1] --> [0] + [1]
[0]

[Algo] 9.2 Selection in expected linear time

RANDOMIZED-SELECT(A, p, r, i)
if p == r
2    then return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
k = q - p + 1
if i == k
6    then return A[q]
else if i < k
8    then return RANDOMIZED-SELECT(A, p, q-1, i)
else
10   return RANDOMIZED-SELECT(A, q+1, r, i-k)

RANDOMIZED-PARTITION 我們在 [Algo]7.3 就已經看過了。我們接下來先分析一下 RANDOMIZED-SELECT。一開始 A[q] 被當作 pivot,因為我們知道 A[q+1 .. r] 裏面的所有 item 都比 A[q] 還要來的大,所以如果我們要挑的 ith order statistic 比 A[q] 小的話,那我們就去 A[p..q-1] 裏面挑,否則的話我們就去 A[q+1..r] 裏面挑。不同於 quicksort,它是 partition 完之後左右兩邊都要繼續遞迴下去,這裡只有一邊會繼續遞迴下去。
RANDOMIZED-SELECTION 的 average-case 是 $\Theta(n)$,worst-case 是在我們每次都很晦氣的只把 A[p..r] 分成一邊為 n-1,另一邊為 1 的狀況,這個時候我們的複雜度就是 $\Theta(n^2)$,這樣即使只是要找 minimum 或 maximum 都很不划算。但是因為這個演算法是 randomized 的,所以沒有任何一種特殊的 input 會導致到這種 worst-case,除非我們運氣真的非常不好。


running time of RANDOMIZED-SELECTION
$T(n)$:對一個長度為 n 的 array A[p..r] 執行 RANDOMIZED-SELECTION 所要花費的 running time
$X_k$:一個 indicator random variable,定義為:$X_k$ = I{ the subarray A[p..q] has exactly k elements },因為我們假設 A[p..q] 中每一個 element 被選為 pivot 的機率都一樣,所以 $E[X_k] = 1/n$。
接下來我們要求的是 $E[T(n)]$ 的值。根據演算法,我們可以知道:
$$T(n) \leq \sum_{k = 1}^n X_k\cdot(T(\max(k-1, n-k)) + O(n))$$
$$E[T(n)] \leq E[\sum_{k = 1}^n X_k\cdot(T(\max(k-1, n-k)) + O(n))]$$
$$= \sum_{k = 1}^n E[X_k\cdot(T(\max(k-1, n-k))] + O(n)$$
$$= \sum_{k = 1}^n E[X_k]\cdotE[T(\max(k-1, n-k))] + O(n)$$ ($X_k$ 跟 $T(\max(k-1, n-k))$ 是彼此獨立的)
$$= \sum_{k = 1}^n \frac{1}{n}\cdotE[T(\max(k-1, n-k))] + O(n)$$
在 $k > \lceil n/2 \rceil$ 的時後,$\max(k-1, n-k) = k-1$,在 $k \leq \lceil n/2 \rceil$ 的時候,$\max(k-1, n-k) = n-k$。當 n 是偶數的時候從 $T(\lceil n/2 \rceil)$ 到 $T(n-1)$ 都會重複兩次,當 n 是奇數的時候,除了 $T(\lfloor n/2 \rfloor)$ 只出現過一次之外,其他每一項都會出現兩次,所以我們可以知道:
$$E[T(n)] \leq \frac{2}{n}\sum_{k=\lfloor n/2 \rfloor}^{n-1}E[T(k)] + O(n)$$

接下來,我們用 substitution method 來解這個遞迴式,假設 $T(n) \leq cn$,其中 c 為一個常數。再假設 $O(n)$ 這一項被 $an$ 給 bound 住,其中 a 為一個常數。
$$E[T(n)] \leq \frac{2}{n}\sum_{k=\lfloor n/2 \rfloor}^{n-1}ck + an = \frac{2c}{n}(\sum_{k = 1}^{n-1}k - \sum_{k = 1}^{\lfloor n/2 \rfloor - 1}k) + an$$
$$= \frac{2c}{n}(\frac{(n-1)n}{2} - \frac{(\lfloor n/2 \rfloor -1)\lfloor n/2 \rfloor}{2}) + an \leq \frac{2c}{n}(\frac{(n-1)n}{2} - \frac{(n/2 -2)(n/2 - 1)}{2}) + an$$
$$=\frac{2c}{n}(\frac{n^2 - n}{2} - \frac{n^2/4 - 3n/2 + 2}{2}) + an = \frac{c}{n}(\frac{3n^2}{4} + \frac{n}{2} - 2) + an$$
$$=c(\frac{3n}{4} + \frac{1}{2} - \frac{2}{n}) + an \leq \frac{3cn}{4} + \frac{c}{2} + an = cn - (\frac{cn}{4} - \frac{c}{2} - an)$$
為了要完成這個證明,我們要保證$cn/4 - c/2 - an \geq 0$ 在 n 足夠大的時候。
$$\frac{cn}{4} - \frac{c}{2} - an \geq 0 \Rightarrow n(c/4 - a) \geq c/2$$
為了要讓它大於 0,所以 $c > 4a$,此時
$$n \geq \frac{c/2}{c/4-a} = \frac{2c}{c-4a}$$
所以只要我們假設在 $n < 2c/(c-4a)$ 的時候 $T(n) = O(1)$,我們就可以得到 $T(n) = O(n)$

[Algo] Exercise 9.1

Exercise 9.1-1
Show that the second smallest of n elements can be found with $n + \lceil\lg n\rceil - 2$ comparisons in the worst case. (Hint: Also find the smallest element.)
solution:
Imagine that each comparison is a match, the minimum is the final champion. As we have already known, it requires at least $n - 1$ comparisons to determine who is the winner. The second place must have been compared to the minimum and defeated. To find who is the second smallest, we can trace each match the minimum played. Gather all these defeated items and pick the smallest among them, it is the very second smallest. The minimum must play $\lceil \lg n\rceil$ games, so there are $\lceil \lg n\rceil$ candidates. To find the second smallest, we require another $\lceil \lg n\rceil - 1$ games. Therefore, there are $n - 1 + \lceil \lg n\rceil - 1 = n + \lceil \lg n\rceil - 2$ comparisons.


Exercise 9.1-2
Show that $\lceil 3n/2 \rceil - 2$ comparisons are necessary in the worst case to find both the maximum and minimum of n numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum, and investigate how a comparison affects these counts.)
solution:
Initially, there are n potential items of maximum candidates and minimum candidates. If $a_i$ and $a_j$ are simultaneous in the candidate set of maximum and minimum respectively, after $a_i$ compares to $a_j$ the cardinality of candidate set of maximum and minimum will decrease by 1. If $a_i$ and $a_j$ are in the candidate set of maximum or minimum, after $a_i$ compares to $a_j$ the cardinality of the set will decrease by 1.
(1) when n is even:
After $n/2$ comparisons, the candidate set of maximum and minimum will remain $n/2$ candidates. Next, it requires $n/2 - 1$ comparisons to determine the maximum and another $n/2 - 1$ comparisons to determine the minimum. Total comparisons needed is $3n/2 - 2 = \lceil 3n/2 \rceil -2$.
(2) when n is odd:
After $(n-1)/2$ comparisons, the candidate set of maximum and minimum will remain $(n+1)/2$ candidates. Next, it requires at most $(n+1)/2 - 1$ comparisons to determine the maximum and another at most $(n+1)/2 - 1$ comparisons to determine the minimum. Total comparisons needed is $3n/2 - 3/2 = \lceil 3n/2 \rceil -2$.

[Algo] 9.1 Minimum and maximum

定義
order statistic:
The ith order statistic of a set of n elements is the ith smallest element.
minimum:
The minimum of a set of elements is the first order statistic (i = 1).
maximum:
The maximum is the nth order statistic (i = n).
lower median:
$i = \lfloor (n + 1)/2 \rfloor$
For simplicity, we consistently use the phrase "the median" to refer to the lower median.
upper median:
$i = \lceil (n + 1)/2 \rceil$


到底要做過幾次 comparison 才能知道誰是 minimum?
@{
\proc{Minimum}(A)
\li min = A[1]
\li \For i = 2 \;\textbf{to}\;\textit{length}[A]
\li \;\;\;\;\If min > A[i]
\li \;\;\;\;\;\;\;\;min = A[i]
\li \Return min
}@


Lower bound: n-1 comparisons
對任何一個演算法來講,決定誰是 minimum 就像一場巡迴賽一樣。想像每一次 comparison 都是一場比賽,兩者中比較小的為獲勝者,每一場比賽都會有一個輸家。除了 minimum 這個人之外,其他每個人一定曾經輸過一場比賽,所以總共至少會有 n-1 場比賽(因為每一個人都要輸過一場比賽嘛),也就是至少會有 n-1 次 comparison。


Simultaneous minimum and maximum
用一個 $\Theta(n)$ 的演算法在一個 array 裏,同時找出 minimum 和 maximum 並不難。但是其實"最多"只要 $3\lfloor n/2 \rfloor$ 次的 comparison 就足夠了。

@{
\proc{Simultaneous-Min-Max}(A)
\li \If \;\textit{length}[A]\;\textup{is odd}
\li \;\;\;\;max\;\textup{and}\;min\;\textup{are initialized to}\;A[1]
\li \Else
\li \;\;\;\;max\;\textup{and}\;min\;\textup{are initialized by comparing}\;A[1]\;\textup{and}\;A[2]
\li i = 2
\li \While i + 1 \leq \textit{length}[A]
\li \;\;\;\;M = \textup{the larger of}\;A[i]\;\textup{and}\;A[i+1]
\li \;\;\;\;m = \textup{the smaller of}\;A[i]\;\textup{and}\;A[i+1]
\li \;\;\;\;\If M > max
\li \;\;\;\;\;\;\;\;max = M
\li \;\;\;\;\If m < min
\li \;\;\;\;\;\;\;\;min = m
\li \;\;\;\;i = i + 2
\li \Return max \;\textup{and}\;min
}@



我們來分析一下這個演算法的複雜度,
(1) 如果 n 是奇數,那 minmax 都被初始為 A[1],接下來每兩個就先做一次 comparison,比較大者就去跟 max 作 comparison,比較小的就去跟 min 作 comparison,所以每一對 A[i] 和 A[i+1] 都會有 3 次 comparison,所以會有 $3 \times (n-1)/2 = 3\lfloor n/2 \rfloor$ 次的 comparison。
(2) 如果 n 是偶數,A[1] 跟 A[2] 先做一次 comparison,那 minmax 先依照 A[1] 跟 A[2] 比較的結果被初始,接下來每兩個就做一次 comparison,道理跟上面差不多。所以每一對 A[i] 和 A[i+1] 都會有 3 次 comparison,所以會有 $3 \times (n-2)/2 + 1 = 3(n/2) - 2 \leq 3\lfloor n/2 \rfloor$ 次的 comparison。

2010年12月24日 星期五

[Algo] Problems 8

Problem 8-1 Average-case lower bounds on comparison sorting
In this problem, we prove an $\Omega(n\lg n)$ lower bound on the expected running time of any deterministic or randomized comparison sort on $n$ distinct input elements. We begin by examining a deterministic comparison sort $A$ with decision tree $T_A$. We assume that every permutation of $A$'s inputs is equally likely.
a. Suppose that each leaf of $T_A$ is labeled with the probability that it is reached given a random input. Prove that exactly $n!$ leaves are labeled $1/n!$ and that the rest are labeled 0.
b. Let $D(T)$ denote the external path length of a decision tree $T$; that is, $D(T)$ is the sum of the depths of all the leaves of $T$. Let $T$ be a decision tree with $k > 1$ leaves, and let $LT$ and $RT$ be the left and right subtrees of $T$. Show that $D(T) = D(LT) + D(RT) + k$.
c. Let $d(k)$ be the minimum value of $D(T)$ over all decision trees $T$ with $k > 1$ leaves. Show that $d(k) = \min_{1 \leq i \leq k-1}\{d(i) + d(k-i) + k\}$. (Hint: Consider a decision tree $T$ with $k$ leaves that achieves the minimum. Let $i_0$ be the number of leaves in $LT$ and $k - i_0$ the number of leaves in $RT$.)
d. Prove that for a given value of $k > 1$ and $i$ in the range $1 \leq i \leq k-1$, the function $i\lg i + (k-i)\lg(k-i)$ is minimized at $i = k/2$. Conclude that $d(k) = \Omega(k\lg k)$.
e. Prove that $D(T_A) = \Omega(n!\lg(n!))$, and conclude that the expected time to sort $n$ elements is $\Omega(n\lg n)$.

Now consider a randomized comparison sort $B$. We can extend the decision-tree model to handle randomization by incorporating two kinds of nodes: ordinary comparison nodes and "randomization" nodes. A randomization node models a random choice of the form RANDOM(1, $r$) made by algorithm $B$; the node has $r$ children, each of which is equally likely to be chosen during an execution of the algorithm.
f. Show that for any randomized comparison sort $B$, there exists a deterministic comparison sort $A$ that makes no more comparisons on the average than $B$ does.
solution:
a.Since all elements are distinct, there are $n!$ permutations of input of $n$ elements and each permutation is equally likely. Therefore, $T_A$ must have at least $n!$ leaves and each of these $n!$ leaves has the same probability. The probability of the rest of leaves are 0, since $1 - n! \times 1/n! = 0$.

b.We define depth($l$, $T$) to be the depth of leaf $l$ of tree $T$. For any leaf $l$ of $T$, if $l$ belongs to $RT$ then depth($l$, $T$) = depth($l$, $RT$) + 1. It is true for $l$ belonging to $LT$. So we can show


c. Consider a decision tree $T$ with $k$ leaves that achieves the minimum. Then $d(k) = D(T)$. By b., we know that $D(T) = D(LT) + D(RT) + k$, thus $d(k) = D(LT) + D(RT) + k$, where $LT$, $RT$ are the left and right subtree of $T$ respectively. We claim that if $T$ achieves the minimum and $LT$ has $i_0$ leaves and $RT$ has $k - i_0$ leaves, then $D(LT) = d(i_0)$ and $D(RT) = d(k - i_0)$. Otherwise, we can construct a decision tree $T'$ by a left subtree $LT'$ with $i_0$ leaves and a right subtree $RT'$ with $k - i_0$ leaves, where $D(LT') = d(i_0)$ and $D(RT') = d(k - i_0)$ such that $D(T') \leq D(T)$. Hence, to find the desired decision tree $T$, we can construct a decision tree iteratively by a left subtree $LT$ such that $D(LT) = d(i_0)$ and a right subtree $RT$ such that $D(RT) = d(k - i_0)$ for $i_0 = 1, 2, \cdots, k-1$ to find the minimum one. So, $d(k) = \min_{1 \leq i \leq k-1}\{d(i) + d(k - i) + k\}$.

d. First, we provide a proof to find the minimum.
We can find the minimum by AM-GM inequality. Since $i\lg i \geq 0$ and $(k-i)\lg(k-i) \geq 0$, then $i\lg i + (k-i)\lg(k-i) \geq 2\sqrt{i\lg i \times (k-i)\lg(k-i)}$. The AM and GM are equal if and only if $i\lg i = (k-i)\lg(k-i)$. Apparently, $i = k/2$ meets the requirement, and by root-finding algorithm ,$i = k/2$ is the only solution. Then, the minimum is $2\sqrt{i\lg i \times (k-i)\lg(k-i)} = 2\sqrt{[(k/2)\lg(k/2)]^2} = k\lg(k/2)$.
Next, we are going to prove that  $d(k) = \Theta(k\lg k)$.
Suppose that $d(k) \leq c_1k\lg k$ for some constant $c_1$.

So we can choose a $c_1 \geq 1$, such that $d(k) \leq c_1k\lg k$.
Suppose that $d(k) \geq c_2k\lg k$ for some constant $c_2$.

So we can choose a $c_2 \leq 1$ such that $d(k) \geq c_2k\lg k$. So we can conclude that $d(k) = \Theta(k \lg k)$.

e. Suppose that $T_A$ has $k$ leaves, where $k \geq n!$. By definition, $D(T_A) \geq d(k) = \Theta(k\lg k) \geq \Theta(n!\lg n!) = \Omega(n!\lg n!)$. The expected running time $E[T_A(n)] \geq D(T_A)/n! = \Omega(n!\lg n!) / n! = \Omega(\lg n!) = \Omega(n\lg n)$.

f. We modify the randomized decision tree to define a deterministic decision tree. At each randomized node, pick the child with the smallest subtree. Delete all the other children and splice out the randomized node itself. The deterministic algorithm corresponding to this modified tree still works, because the randomized algorithm worked no matter which path was taken from each randomized node. The average number of comparisons for the modified algorithm is no larger than the average number for the original randomized tree, since we discarded the high-average subtrees in each case.


Problem 8-2 Sorting in place in linear time
Suppose that we have an array of $n$ data records to sort and that the key of each record has the  value 0 or 1. An algorithm for sorting such a set of records might possess some subset of the following three desirable characteristics:
1. The algorithm runs in $O(n)$ time.
2. The algorithm is stable.
3. The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.
a. Give an algorithm that satisfies criteria 1 and 2 above.
b. Give an algorithm that satisfies criteria 1 and 3 above.
c. Give an algorithm that satisfies criteria 2 and 3 above.
d. Can any of your sorting algorithms from parts (a)-(c) be used to sort $n$ records with b-bit keys using radix sort in $O(bn)$ time? Explain how or why not.
e. Suppose that the $n$ records have keys in the range from 1 to k. Show how to modify counting sort so that the record can be sorted in place in $O(n+k)$ time. You may use $O(k)$ storage outside the input array. Is your algorithm stable? (Hint: How would you do it for $k=3$ ?)
solution:
a. counting sort
b. partition
c. insertion sort
d. part (a) -- counting sort. Counting sort runs in $O(n)$ times, and for b-bit keys with each bit value varies from 0 to 1, we can sort in $O(b(n + 2)) = O(bn)$ time.
e.We propose a modified counting sort algorithm that not only sorts in place in $O(n+k)$ time but also is stable. The algorithm requires two arrays of length $k$.
@{
\proc{Counting-Sort}^{'}(A, k)
\li \textup{initialize}\;C1[0..k] = 0
\li \For j = 1 \;\textbf{to}\;\textit{length}[A]
\li \;\;\;\;C1[A[j]] = C1[A[j]] + 1
\li \For i = 1 \;\textbf{to}\;k
\li \;\;\;\;C1[i] = C1[i] + C1[i - 1]
\li \For i = 0\;\textbf{to}\;k
\li \;\;\;\;C2[i] = C1[i]
\li \For i = \textit{length}[A]\;\textbf{downto}\; 1
\li \;\;\;\;\If i > C2[A[i]]
\li \;\;\;\;\;\;\;\;a = A[i]
\li \;\;\;\;\;\;\;\;\textbf{do}
\li \;\;\;\;\;\;\;\;\;\;\;\;j = C1[a]
\li \;\;\;\;\;\;\;\;\;\;\;\;b = A[j]
\li \;\;\;\;\;\;\;\;\;\;\;\;A[j] = a
\li \;\;\;\;\;\;\;\;\;\;\;\;C1[a] = C1[a] - 1
\li \;\;\;\;\;\;\;\;\;\;\;\;a = b
\li \;\;\;\;\;\;\;\;\While C1[a] \not= i
\li \;\;\;\;\;\;\;\;A[i] = a
}@

C1 acts just like array C in the original counting sort algorithm. C2 is the additional array that keeps the important information. C2[i] is the maximum index that i can take up. While we look up each element in A in a reverse way, if we find out that A[i] > C2[A[i]], A[i] must be put in a wrong position. Then we put A[i] in a correct position by C1[A[i]]. Once each element is put into its correct position, it will never be accessed anymore. Thus, the total running time is $O(n + k)$, where $k$ is the time we set up the array C1 and C2.


Problem 8-3 Sorting variable-length items
a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is $n$. Show how to sort the array in $O(n)$ time.
b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the string is $n$. Show how to sort the strings in $O(n)$ time. (Note that the desired order here is the standard alphabetical order; for example, a < ab < b.)
solution:
a. Without loss of generality, we assume that all integers are positive. Since numbers with longer bits are always greater than ones with shorter bits, we can group all the numbers by their bit length. The longest bit length is n, and the shortest bit length is 1. Let $m_i$ be the number of integers of i bits. We know that $\sum_{i = 1}^n i \cdot m_i = n$. We can look over each number to figure out how many bits does it have, and it takes $O(n)$ time. Next, for each group, we can sort the numbers by radix sort. The total time is $O(n)$.

b. When a string x and a string y are compared, if the first letter of a string x is lexicographically greater than the first letter of a string y, then x is lexicographically greater than y. We can sort the strings on the first letter, and gather strings with the same first letter into groups. The empty strings are taken out and put first. Then, the sorting is recursive within each group after the first letter is removed. Finally, all strings will be sorted.
We analyze the running time of the sorting process. The $m_i$ denotes the number of strings of i characters. And we have $\sum_{i = 1}^n i \cdot m_i = n$. For a string s with l characters, it will be sorted by counting sort l times. For example, if there are $t_i$ strings with i characters and the total characters over all strings is T, then the total cost to call counting sort is $\sum_i O(t_i) = O(\sum_i t_i) = O(T)$. Thus, the overall running time is $O(n)$.


Problem 8-4 Water jugs
Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa.
It is your task to find a grouping of the jugs into pair of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or if they are of the same volume.  Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs.
a. Describe a deterministic algorithm that uses $\Theta(n^2)$ comparisons to group the jugs into pairs.
b. Prove a lower bound of $\Omega(n\lg n)$ for the number of comparisons an algorithm solving this problem must take.
c. Give a randomized algorithm whose expected number of comparisons is $O(n\lg n)$, and prove that this bound is correct. What is the worst-case number of comparisons for your algorithm.
solution:
a. For each red jug, we pick every blue jug to compare directly. The algorithm is a double-nested for loop, so the total running time is $O(n^2)$.

b. We can view this problem as a decision tree model. Each node is labeled with two jugs, and the leaves are labeled with a unique matching. Each node has three children, each stands for red jug is smaller, equal size, and red jug is larger. Let h be the height of the decision tree, then we can obtain $3^h \geq n! \Rightarrow h \lg 3 \geq \lg n! \Rightarrow h \geq \Omega(n\lg n)$.

c. We propose a randomized algorithm whose expected number of comparison is $O(n\lg n)$.
@{
\proc{Match-Jugs}(R,B)
\li \If |R|=0
\li \;\;\;\;\Return
\li \If |R|=1
\li \;\;\;\;\textup{let}\;R=\{r\},B=\{b\}
\li \;\;\;\;\textup{output "}(r,b)\textup{"}
\li \;\;\;\;\Return
\li \Else
\li \;\;\;\;r=\;\textup{a randomly chosen jug in}\;R
\li \;\;\;\;B_{<}=\{b | b \in B, \;\textup{and}\;b < r\}
\li \;\;\;\;B_{>}=\{b | b \in B, \;\textup{and}\;b > r\}
\li \;\;\;\;b = \;\textup{the one jug in}\;B\;\textup{with the same size as}\;r
\li \;\;\;\;R_{<} = \{r | r \in R, \;\textup{and}\;r < b\}
\li \;\;\;\;R_{>} = \{r | r \in R, \;\textup{and}\;r > b\}
\li \;\;\;\;\textup{output "}(r,b)\textup{"}
\li \;\;\;\;\proc{Match-Jugs}(R_{<}, B_{<})
\li \;\;\;\;\proc{Match-Jugs}(R_{>}, B_{>})
}@


What about the running time? Let us order the jugs as $r_1, r_2, \ldots, r_n$ and $b_1, b_2, \ldots, b_n$ where $r_i < r_{i+1}$ and $b_i < b_{i+1}$ for $i = 1, 2, \ldots, n$, and $r_i = b_i$. Our analysis uses indicator random variables
$X_{ij} = \mbox{I}\{\mbox{red jug } r_i \mbox{ is compared to blue jug } b_j\}}$.
As in quicksort, a given pair $r_i$ and $b_j$ is compared at most once. When we compare $r_i$ to every jug in B, jug $r_i$ will not be put in either $R_<$ or $R_>$. When we compare $b_i$ to every jug in $R-\{r_i\}$, jug $b_i$ is not put into either $B_<$ or $B_>$. The total number of comparison is
$$X = \sum_{i = 1}^{n-1}\sum_{j = i + 1}^{n}X_{ij}.$$
To calculate the expected value of X, we follow the quicksort analysis to arrive at
$$E[X] = \sum_{i = 1}^{n-1}\sum_{j = i + 1}^{n} \mbox{Pr}\{r_i \mbox{ is compared to } b_j\}.$$
As in the quicksort analysis, once we choose a jug $r_k$ such that $r_i < r_k < b_j$, we will put $r_i$ in $R_<$ and $b_j$ in $R_>$, and so $r_i$ and $b_j$ will never be compared again. Let us denote $R_{ij} = \{r_i, \ldots, r_j\}$. Then jugs $r_i$ and $b_j$ will be compared if and only if the first jug in $R_{ij}$ to be chosen is either $r_i$ or $r_j$.
Still following the quicksort analysis, until a jug from $R_{ij}$ is chosen, the entire set $R_{ij}$ is together. Any jug in $R_{ij}$ is equally likely to be first one chosen. Since $|R_{ij}| = j - i + 1$, the probability of any given jug being the first one chosen in $R_{ij}$ is $1 / (j - i + 1)$. The remainder of the analysis is the same as the quicksort analysis, and we arrive at the solution of $O(n\lg n)$ comparisons.
Just like in quicksort, in the worst case we always choose the largest (or smallest) jug to partition the sets, which reduces the set sizes by only 1. The running time then obeys the recurrence $T(n) = T(n - 1) + \Theta(n)$, and the number of comparisons we make in the worst case is $T(n) = \Theta(n^2)$.


Problem 8-5 Average sorting
Suppose that, instead of sorting an array, we just require that the elements increase on average. More precisely, we call an n-element array A k-sorted if, for all $i = 1, 2, \ldots, n-k$, the following holds:
$$\frac{\sum_{j = i}^{i + k - 1}A[j]}{k} \leq \frac{\sum_{j = i + 1}^{i + k}A[j]}{k}.$$
a. What does it mean for an array to be 1-sorted?
b. Give a permutation of the numbers 1, 2, ..., 10 that is 2-sorted, but not sorted.
c. Prove that an n-element array is k-sorted if and only if $A[i] \leq A[i + k]$ for all $i = 1, 2, \ldots, n-k$.
d. Giva an algorithm that k-sorts an n-element array in $O(n\lg(n/k))$time.

We can also show a lower bound on the time to produce a k-sorted array, when k is a constant.
e. Show that a k-sorted array of length n can be sorted in $O(n\lg k)$ time. (Hint: Use the solution to Exercise 6.5-8.)
f. Show that when k is a constant, it requires $\Omega(n\lg n)$ time to k-sort an n-element array. (Hint: Use the solution to the previous part along with the lower bound on comparison sorts.)
solution:
a. By definition, $A[i] \leq A[i+1]$ for $i = 1, 2, \ldots, n$.

b. [2, 1, 4, 3, 6, 5, 8, 7, 10, 9]

c. array A is k-sorted if, for all i,


d. We can modify quicksort algorithm to perform k-sorting an array. The line 1 in QUICKSORT is modified to if p + (k - 1) < r. The algorithm stops splitting when the length of the array is less than or equal to k. Because the array is split such that items in left hand side are less than right hand side, we always satisfy the condition in the above problem. The recursion tree will have height of $\Theta(\lg(n/k))$. So the total running time is $O(n\lg(n/k))$.

e. Without loss of generality, we assume that $n = km$. That is, an n-element array can be divide into m group of length k. The first element of each group can form a sorted list. The second element of each group form a sorted list as well and so on. By Exercise 6.5-8, we can merge these $(n/k)$ sorted list into a sorted list in $O(n\lg(n/k))$ time.

f. Consider a decision tree model that simulates k-sorting an array. Its nodes are just like the original decision tree we know. Except that its leaves label with a unique match of k-sorted result. Let the height of the decision tree be h. Permutations of k-sort array is
$$C_k^n\times C_k^{n-k}\times\cdots C_k^k = \frac{n!}{k!(n-k!)}\times\frac{(n-k)!}{k!(n-2k)!}\times\cdots\times\frac{k!}{0!k!} = \frac{n!}{(k!)^{n/k}}.$$
So we have
$$2^h \geq \frac{n!}{(k!)^{n/k}} \geq \frac{(n/e)^n}{(k!)^{n/k}} = (\frac{n}{e(k!^{1/k})})^n.$$
Since k is a constant, we can obtain that
$$h \geq n\lg\frac{n}{c} = \Omega(n\lg n),$$
where $$c = e(k!)^{1/k}$$ is a constant.
Therefore,  it requires $\Omega(n\lg n)$ time to k-sort an n-element array.


Problem 8-6  Lower bound on merging sorted lists
The problem of merging two sorted lists arises frequently. It is used as a subroutine of MERGE-SORT, and the procedure to merge two sorted lists is given as MERGE in section 2.3.1. In this problem, we will show that there is a lower bound of $2n-1$ on the worst-case number of comparisons required to merge two sorted lists, each containing n items.
First we will show a lower bound of $2n - o(n)$ comparisons by using a decision tree.
a. Show that, given 2n numbers, there are $C^{2n}_n$ possible ways to divide them into two sorted lists, each with n numbers.
b. Using a decision tree, show that any algorithm that correctly merges two sorted lists uses at least $2n - o(n)$ comparisons.
Now we will show a slightly tighter $2n - 1$ bound.
c. Show that if two elements are consecutive in the sorted order and from opposite lists, then they must be compared.
d. Use your answer to the previous part to show a lower bound of $2n - 1$ comparisons for merging two sorted lists.
solution:
a. trivial
b. Let the height of the decision tree be h. The decision tree contains at least $C^{2n}_n$ leaves.
By Stirling's formula, we know that
$$n! = \sqrt{2\pi n}(\frac{n}{e})^ne^{\alpha_n},$$
where
$$\frac{1}{12n+1} < \alpha_n < \frac{1}{12n}.$$
Then,



c. Let the two sorted array be A and B, and $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ are elements of A and B respectively.Suppose that $a_i$ and $b_j$ are adjacent in final sorted list.
$\cdots, a_{i-1}, a_i, a_{i+1}, \cdots$
$\cdots, b_{j-1}, b_j, b_{j+1}, \cdots$
If $b_j$ compares to $a_k$ where $k = 1, \ldots, i-1$, the result must be $a_k \leq b_j$ but we are not able to determine the whether $b_j$ is greater than $a_i$ or not. Similarly, if $b_j$ compares to $a_K$ where $K = i+1, \ldots, n$, we cannot know that if $b_j$ is greater than $a_i$ or not, either. Therefore, the only way we figure out the order of $b_j$ and $a_i$ in the final sorted list is comparing $b_j$ to $a_i$ directly.

d. We consider a worst-case to determine the lower bound. Let $a_1, a_2, \ldots, a_{2n}$ be a sorted list, and $A = \langle a_1, a_3, \ldots, a_{2n-1}\rangle$, $B = \langle a_2, a_4, \ldots, a_{2n}\rangle$. By problem c, we know that $a_i$ must compare to $a_{i+1}$ in the merging process. So, there must be at least $2n-1$ comparisons.

2010年12月6日 星期一

[Algo] Exercise 8.4

Exercise 8.4-2
What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time $O(n \lg n)$?
solution:
The worst-case is that all elements are distributed in the same bucket, consequently, $O(n^2)$ running time is required to perform insertion sort. A simple change is to replace insertion sort with any $O(n \lg n)$ sorting algorithm, such as merge sort, quicksort, etc. to improve running time from $O(n^2)$ to $O(n \lg n)$.


Exercise 8.4-3
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?
solution:
$E[X^2] = 0 \times 1/4 + 1^2 \times 1/2 + 2^2 \times 1/4 = 1/2 + 1 = 3/2$
$E^2[X] = (0 \times 1/4 + 1 \times 1/2 + 2 \times 1/4)^2 = (1/2 + 1/2)^2 = 1$


Exercise 8.4-4
We are given n points in the unit circle, $p_i = (x_i, y_i)$, such that $0 < x_i^2 + y_i^2 \leq 1$ for $i = 1, 2, \ldots, n$. Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design a $\Theta(n)$ expected-time algorithm to sort the n points by their distances $d = \sqrt{x_i^2 + y_i^2}$ from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)
solution:
Note that the expected number of points residing in an area is proportional to the size of the area. To satisfy the assumption of BUCKET-SORT, we have to make the interval $(0, 1]$ split in a proper way. Consider a distance $d$ between $a$ and $b$, where $0 \leq a < d < b \leq 1$. The area is $\pi(b^2 - a^2)$. Dividing $(0, 1]$ into n equal-sized intervals does not help a lot. It does not mean we divide a unit circle into n areas evenly. To achieve our goal, we divide $(0, 1]$ into $<0, \sqrt{1/n}, \sqrt{2/n}, \ldots, \sqrt{n-1/n}, 1>$ intervals instead. In the context of such dividing, we can see that the $\pi(1/n) = \pi((\sqrt{2/n})^2 - (\sqrt{1/n})^2) = \cdots = \pi(1 - (\sqrt{n-1/n})^2)$. Because of the equal size of area, we'll expect that each bucket contain roughly the same points.


Exercise 8.4-5
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) = \mbox{Pr}\{X \leq x\}$. Suppose that a list of $n$ random variables $X_1, X_2, \ldots, X_n$ is drawn from a continuous probability function $P$ that is computable in $O(1)$ time. Show how to sort these numbers in linear expected time.
solution:
$P(x)$ is defined in a manner of cumulative distribution function. By probability integral transform, we know that $P(X_i)$ has a uniform distribution, where $i = 1, 2, \ldots, n$. As a result, we can sort these transformed numbers by BUCKET-SORT in linear time.