- Git 是 Distributed Version Control System (DVCS)，每次 client 不只是從 repository 拿到最新版本的檔案而已，而是整個 repository 都整個備份下來 (包含從頭到尾的版本)，不用擔心任何一台 server 掛掉的狀況，因為每個人都是 repository。
- 大部分的 Version Control System (VCS) 都是儲存每一版本之間檔案的變化，如果要第 r 版的檔案，只要第 1 版的檔案，跟第 1 版到第 r 版的檔案的變化，就可以還原第 r 版的檔案長什麼樣，然而 Git 是紀錄整個檔案下來，而不是只儲存檔案的變化。
- 因為整個 repository 都在你的電腦裡面，所以每次 commit 或絕大部分的 operation 都在自己的電腦裡面就完成了，不用靠網路連線連到遠端的 server 去完成 commit 或看 log 等之類的動作。
- Git 在儲存檔案前會做 check sum (SHA-1 hash)，事實上 Git 不是靠檔名來儲存檔案的，而是靠這些 hash value
- 在 Git 裡，檔案會被歸類到三種狀態之一：
- commited：檔案已經被安全的儲存到電腦中的 database 裡了
- modified：你已經改變過檔案的內容了，但是還沒 commit 到你的 database 裡面
- staged：標示這個修改過的檔案，準備把它 commit 到 database 裡
2011年1月28日 星期五
[Git] 01_認識 Git
2011年1月25日 星期二
[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^{'})
}@
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^{'})
}@
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)$.
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:
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.
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.
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)
1 n = r - p + 1
2 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)
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)
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)$ 的演算法。
這一個 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:
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]
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)
1 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)
1 if p == r2 then return A[p]
3 q = RANDOMIZED-PARTITION(A, p, r)
4 k = q - p + 1
5 if i == k
6 then return A[q]
7 else if i < k
8 then return RANDOMIZED-SELECT(A, p, q-1, i)
9 else
10 return RANDOMIZED-SELECT(A, q+1, r, i-k)
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$.
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$.
訂閱：
文章 (Atom)