- 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^{'})
}@
訂閱：
文章 (Atom)