# HW-1

### 1
> Recall the recursive program (discussed in the class) that computes the $n$-th Fibonacci number. Compute the exact number of additions used by the program.

令 $T(n)$ 為計算第 n 個費氏數所需的加法次數，則根據遞迴公式可得 $T(n)=T(n-1)+T(n-2)+1, T(1)=0,T(2)=0,T(3)=1$
$T(n)=T(n-1)+T(n-2)+1\leq2T(n-1)+1$

$$
\begin{split}
T(n)&\leq2T(n-1)+1\\
&=2[2T(n-2)+1]+1\\
&=2^2T(n-2)+2+1\\
&=2^2[2T(n-3)+1]+2+1\\
&=2^3T(n-3)+2^2+2+1=...\\
&=2^kT(n-k)+2^{k-1}+2^{k-2}+...+2^2+2+1=2^kT(n-k)+\dfrac{1-2^k}{1-2}\\
&=2^kT(n-k)+2^k-1 \ \ (let \ n-k=1)\\
&=2^{n-1}T(1)+2^{n-1}-1=2^{n-1}-1=O(2^n)
\end{split}$$
故 $T(n)\in O(2^n)$

---

### 2
> Given a tree T and k subtrees of T such that each pair of subtrees has at least one vertex in common, prove that there is at least one vertex in common to all the subtrees.

**解法一 :**
令$k=2$，$T_1$與$T_2$為$T$的subtree，根據題目給定條件，$T_1$與$T_2$至少有一個共同頂點，因此當$k=2$時成立。

假設$k=m$，如果任意一組subtree $T_1,T_2,...,T_m$至少有一個共同的頂點，那麼存在至少一個頂點為subtree $T_1,T_2,...,T_m$的共同頂點。

令$k=m+1$，要證明任意一組subtree $T_1,T_2,...,T_{m+1}$至少有一個共同的頂點的條件下，至少存在一個全部subtree的共同頂點。
由於任意一組subtree $T_1,T_2,...,T_m$至少有一個共同的頂點，且存在至少一個頂點為subtree $T_1,T_2,...,T_m$的共同頂點，因此我們只需要考慮subtree $T_{m+1}$與$T_1,T_2,...,T_m$之間的關係。由於$T_{m+1}$與任一一個subtree至少有一個共同頂點，且在$T_1,T_2,...,T_m$存在一個共同頂點，因此$T_{m+1}$也存在一個與$T_1,T_2,...,T_m$共同的頂點。

根據數學歸納法，在一個tree中有$k$個subtree使得每一組subtree中至少存在一個頂點，那麼在所有subtree中必定存在至少一個共同的頂點。

**解法二** :
題目等同於證明 Helly property 的定理

**Helly property** : A family $\{A_i:i \in I\}$ of subsets of a set A is said to satisfiy the Helly property if $J\subseteq I$, and $A_i\cap A_j \neq \varnothing$, for every $i, j \in J$, then $\bigcap_{j\in J}A_j\neq\varnothing$.
**Theorem : A family of subtrees of a tree satisfies the Helly property 一棵樹的所有子樹皆滿足 Helly property**

**Proof**:
令 A 收集的是樹 T 的所有子樹，$A=\{T_i:i \in I=\{1, 2, ..., n\}\}$。假設對所有的 $i, j \in J=\{1, 2, ...,k\}\subseteq I, T_i \cap T_j \neq \varnothing$，我們需要證明出 $\bigcap_{j\in J}T_j\neq\varnothing$。
若有一棵子樹 $T_i \in A, i \in J$ 只有一個點 $v$，則明顯可證出 $\bigcap_{j\in J}T_j=\{v\}$。所以假設每個子樹 $T_i \in A, i \in J$ 至少有兩個節點。

我們對子樹的節點數進行歸納法。假設樹 T 有 n 個節點，每個子樹最多有 n 個節點，且滿足 Helly property。
當 T 為 n + 1 個節點的樹時，
令 $v_0$ 為 T 的樹葉節點且其唯一的鄰點為 $u$。
令 $T_i'=T_i-v_0，i \in J$ 且 $T'=T-v_0$ 為 n 個節點的樹。
($T_i'$ 為 T 的子樹去除 $v_0$，所以最多有 n 個節點)

根據歸納假設，$T'$ 滿足 Helly Property。
1. 若 $T_i\ 和 \ T_j$ 有一共同點 $x(\neq v_0)$，則 $T_i'\ 和 \ T_j'$ 一定也有一共同點 $x$。
2. 若 $T_i\ 和 \ T_j$ 有一共同點 $v_0$，則 $T_i\ 和 \ T_j$ 一定還有一共同點 $u_0$，因為前面有假設子樹最少兩個節點，所以如果 $v_0$ 在裡面，$u_0$ 勢必也一定會在裡面，不然其中一個子樹只有一個節點 $v_0$ 會矛盾。
$\Rightarrow$ $T_i'\ 和\ T_j'$ 有一個共同點 $u_0$

由 (1)(2) 根據歸納假設，因為 $T_i'\cap T_j'\neq \varnothing,$，則 $\bigcap_{j\in J}T_j'\neq \varnothing$，也因此每個 $T_j'$ 再加入 $v_0$ 得到 $\bigcap_{j\in J}T_j\neq \varnothing$。所以當 T 的節點數為 n + 1時命題亦成立，故由數學歸納法可得證。

### 3
> The lattice points in the plane are the points with integer coordinate. Consider a polygon that all of its vertices are lattice points. Let $p$ be the number of lattice points that are on the boundary of the polygon, and let $q$ be the number of lattice points that are inside the polygon. Prove that the area of the polygon is $p/2+q-1$.

想法：先考慮簡單的 case (已有面積公式的圖形，如3 or 4邊形)，並以此基礎假設 $n-1$ 多邊形的面積成立，並推出 $n$ 多邊形的面積成立。

首先，我們先考慮矩形 case，對任意滿足題意的 $m*n$ 的矩形，皆有 $p = 2m+2n$ (邊界點) 且 $q = (m-1)(n-1)$，其中 $m$、$n$ 為矩形的邊長，且已知矩形面積為 $mn$，故
$$
\begin{align}
q + p/2 - 1 &= (m-1)(n-1) + 2(m+n)/2 - 1\\
&= (mn-m-n+1) + (m+n) - 1\\
&= mn
\end{align}
$$

接著，考慮直角三角形的 case ，對任意滿足題意直角三角形，令其兩股長為 $m, n$ ，並且可將其視為，滿足題意的 $m*n$ 的矩形的一半，故其面積為 $mn/2$ ，但我們並不知道直角三角形的斜邊上有多少點，故我們假設有 $k$ 個(不包含直角三角形的頂點)，故有 $p = (m + n + 1) + k$，內部點則為在將對角線加到矩形之前，有 $(m − 1)(n − 1)$ 個內部點。 如果從中減去邊界上的 $k$ 個點，則剩餘部分會被對角線分成兩半，因此直角三角形總共有 ((m − 1)(n − 1) − k)/2 個內部點，故

$$
\begin{align}
q + p/2 - 1 &= \frac{(m-1)(n-1)-k}{2} + \frac{m+n+1+k}{2} - 1\\
&= \frac{mn}{2} - \frac{m}{2} - \frac{n}{2} + \frac{1}{2} - \frac{k}{2} + \frac{m}{2} + \frac{n}{2} + \frac{1}{2} + \frac{k}{2} - 1\\
&= \frac{mn}{2}
\end{align}
$$

再考慮任意的三角形，令有一個任意三角形 $T$ 有 $q_t$ 個內點和 $p_t$ 個邊界點，可以透過添加幾個直角三角形 $A, B, C$ 將其擴展為矩形 $R$，假設三角形 $A$ 有 $q_a$ 個內點和 $p_a$ 個邊界點，三角形 $B$ 有 $q_b$ 個內點和 $p_b$ 個邊界點，三角形 $C$ 有 $q_c$ 個內點和 $p_c$ 個邊界點。矩形 $R$ 則有 $q_r$ 個內點和 $p_r$ 個邊界點。且我們知道此公式對於直角三角形和矩形是成立的，故我們有下列的等式

$$
\begin{align}
A = q_a + p_a/2 - 1\\
B = q_b + p_b/2 - 1\\
C = q_c + p_c/2 - 1\\
R = q_r + p_r/2 - 1
\end{align}
$$
且
$$
\begin{align}
T &= R - A - B - C\\
&= q_r-q_a-q_b-q_c + (p_r-p_a-p_b-p_c)/2 + 2
\end{align}
$$
且
$$
\begin{align}
p_a+p_b+p_c = p_r-p_t
\end{align}
$$
與
$$
\begin{align}
q_r &= q_a+q_b+q_c+q_t + (p_a+p_b+p_c-p_r) - 3\\
&= q_a+q_b+q_c+q_t + p_t - 3
\end{align}
$$
故綜合上式可得，
$$
\begin{align}
T &= q_r-q_a-q_b-q_c + (p_r-p_a-p_b-p_c)/2 + 2\\
&= (q_a+q_b+q_c+q_t + p_t - 3) - q_a - q_b - q_c + ((p_a+p_b+p_c-p_t)-p_a-p_b-p_c)/2 + 2\\
&= q_t + p_t - 3 - p_t/2 + 2\\
&= q_t + p_t/2 - 1
\end{align}
$$
最終，在此我們已有對任意 $3, 4$ 邊形此公式皆成立，故我們假設此公式對任意 $n-1$ 邊行皆成立，以此證明對任意 $n$ 邊形亦成立，因此假設我們有一個任意的 $n$ 邊形圖形 $N$ 有 $Q$ 個內點和 $P$ 個邊界點，我們將其兩個頂點做連線，可得兩個子多邊形 $N_1, N_2$，分別有 $Q_1, Q_2$ 個內點和 $P_1, P_2$ 個邊界點，並假設兩個子多邊形的共用邊有 $m$ 個點，則
$$
\begin{align}
Q &= Q_1 + Q_2 + (m − 2)\\
P &= P_1 + P_2 − 2(m − 2) − 2
\end{align}
$$
故
$$
\begin{align}
Q + P/2 - 1 &= (Q_1 + Q_2 + (m − 2)) + (P_1 + P_2 − 2(m − 2) − 2)/2 - 1\\
&= (Q_1 + P_1/2 - 1) + (Q_2 + P_2/2 - 1)\\
&= N
\end{align}
$$
因此，由數學歸納法得證，對任意 $n$ 邊形，其面積為 q + p/2 - 1

**基本三角形的證明 :**

---
### 4
> Given a positive integer n, find a way to partition n into one or more positive integers j1, j2, … , jk (i.e. j1 + j2 + … + jk = n) such that the product of these integers is maximized. Prove the correctness of your formula.

如果一個數拆成兩個數字相加，要使這兩個數字的乘積最大，則這兩個數字一定相等。同理，將數字 n 要拆成多個等份的 x 相加，即 x + x + … + x = n，則乘積最大值為 $x^{\frac{x}{n}}$。

令 $f=x^{\frac{x}{n}}$，利用微分求出極值，得出當 x = e 時 f 會有最大值。因為 2 < e < 3，所以將一個數字拆成 2 和 3 的線性組合時，這些 $j_i$ 的乘積會最大。

另外，6 = 3 + 3 = 2 + 2 + 2，但 3 * 3 > 2 * 2 * 2，所以每拆出三個 2 可以用二個 3 去替換。因此在分割 n 時， $j_i$ 會以 3 為主。

首先，將 n mod 3 找出餘數是多少 :
若餘數為 0，則最大值為 $3^{\frac{n}{3}}$。
若餘數為 1，將 1 和最後一個 3 組合成 4，並把 4 拆成 2, 2，因為 $3 * 1 < 2 * 2$，得到最大值為 $3^{\lfloor\frac{n}{3}\rfloor-1}*2*2$
若餘數為 2，則最大值為 $3^{\lfloor\frac{n}{3}\rfloor}*2$

---
### 5
> Let $a_1, a_2, … , a_n$ be positive real numbers such that $a_1 a_2 \dots a_n = 1$. Prove, without using the arithmetic versus geometric inequality, that $(1+a_1) (1+a_2) \dots (1+a_n) \geq 2^n$.

令$n=1$，由於$a_1 a_2 \dots a_n = 1$，因此當$n=1$時，$a_1=1$，故$1+a_1\geq 2$。

令$n=2$, 由於$a_1 a_2=1$且$a_1,a_2$為正整數
$$
\begin{align}
(1+a_1) (1+a_2) &= 1+a_1+a_2+a_1a_2 \\
&= 2+a_1+a_2 \\
&\geq 2+2 \text{ (AM-GM ineq.)}
\end{align}
$$
因此當$n=2$成立。

假設$n=m$ 時，$(1+a_1) (1+a_2) \dots (1+a_m) \geq 2^m$成立。

$$
\begin{align}
(1+a_1) (1+a_2) \dots (1+a_m) &\geq 2^m \\
(1+a_1) (1+a_2) \dots (1+a_{m+1}) &\geq 2^m (1+a_{m+1}) \\
&\geq 2^m+2^m a_{m+1}
\end{align}
$$

由於$a_1 a_2 \dots a_n = 1$，當$n=m+1$時，$a_{m+1} = \frac{1}{a_1a_2...a_m}=1$。

帶入$a_{m+1}$得
$$
\begin{align}
(1+a_1) (1+a_2) \dots (1+a_{m+1})
&\geq 2^m+2^m \\
&\geq 2^{m+1}
\end{align}
$$

根據數學歸納法，$(1+a_1) (1+a_2) \dots (1+a_n) \geq 2^n, \forall a_i \in \displaystyle \mathbb {R} _{>0}, i\in\{1,2,...,n\}$。


Also can be proven using Jensun ineq. (ignore the weird arrow)

---
### 6
> Given $n \geq 1$ numbers $x_1, x_2, \cdots, x_n$, show that the function $f(x) = \sum_{1 \leq i \leq n}|x - x_i|$ takes its minimum value at the median of these $n$ number.

**數歸證明**

**複雜版**
令 $M$ 為 $x_i$ 的中位數，並將 $x_i$ 作排序，
$$
x_1 \leq x_2 \leq \cdots \leq x_s \leq A \leq x_{s+1} \leq \cdots \leq x_t \leq M \leq x_{t+1} \leq \cdots \leq x_n
$$
考慮 $n$ 是偶數，且 $A \leq M$, $n=2t$，故
$$
\begin{align}
f(A) &= \sum_{i=1}^{s}(A-x_i) + \sum_{i=s+1}^{n}(x_i-A)\\
&= \sum_{i=1}^{t}(A-M+M-x_i) - \sum_{i=s+1}^{t}(A-x_i) + \sum_{i=t+1}^{n}(x_i-M+M-A) + \sum_{i=s+1}^{t}(x_i-A)\\
&= \sum_{i=1}^{t}(M-x_i) + t(A-M) + \sum_{i=t+1}^{n}(x_i-M) + (n-t)(M-A) + 2\sum_{i=s+1}^{t}(x_i-A)\\
&= \sum_{i=1}^{t}(M-x_i) + \sum_{i=t+1}^{n}(x_i-M) + 2\sum_{i=s+1}^{t}(x_i-A) + (n-2t)(M-A)
\end{align}
$$
可以看出前兩項都會大於等於零，且最後一項等於零 (因為 $n=2t$)，故當 $A=M$ 時，$2\sum_{i=s+1}^{t}(x_i-A)$ 會有最小值。

令 $M$ 為 $x_i$ 的中位數，並將 $x_i$ 作排序，
$$
x_1 \leq x_2 \leq \cdots \leq x_s \leq A \leq x_{s+1} \leq \cdots \leq x_t = M \leq x_{t+1} \leq \cdots \leq x_n
$$
考慮 $n$ 是奇數，且 $A \leq M$, $n=2t-1$，故
$$
\begin{align}
f(A) &= \sum_{i=1}^{s}(A-x_i) + \sum_{i=s+1}^{n}(x_i-A)\\
&= \sum_{i=1}^{t}(A-M+M-x_i) - \sum_{i=s+1}^{t}(A-x_i) + \sum_{i=t+1}^{n}(x_i-M+M-A) + \sum_{i=s+1}^{t}(x_i-A)\\
&= \sum_{i=1}^{t}(M-x_i) + t(A-M) + \sum_{i=t+1}^{n}(x_i-M) + (n-t)(M-A) + 2\sum_{i=s+1}^{t}(x_i-A)\\
&= \sum_{i=1}^{t}(M-x_i) + \sum_{i=t+1}^{n}(x_i-M) + 2\sum_{i=s+1}^{t}(x_i-A) + (n-2t)(M-A)\\
&= \sum_{i=1}^{t}(M-x_i) + \sum_{i=t+1}^{n}(x_i-M) + 2\sum_{i=s+1}^{t-1}(x_i-A) + 2(x_t-A) - (M-A)\\
&= \sum_{i=1}^{t}(M-x_i) + \sum_{i=t+1}^{n}(x_i-M) + 2\sum_{i=s+1}^{t-1}(x_i-A) + (M-A)
\end{align}
$$
可以看出前兩項都會大於等於零，故當 $A=M$ 時，$2\sum_{i=s+1}^{t-1}(x_i-A) + (M-A)$ 會有最小值。
當 $A \geq M$ 亦成立。

---
### 7
> Given a set of n +1 numbers out of the first 2n natural numbers 1, 2, …, 2n, prove by mathematic induction that here are two numbers in the set, one of which divides the other.

當 n = 1 時，取 1 和 2，1 | 2，命題成立
假設當 $n=k\geq1$ 命題成立，即從 1, 2, …, 2k 中選 k + 1 個數字，必存在兩個數為倍數關係。
當 $n=k+1$ 時，要從 1, 2, …, 2k + 2 中選 k + 2 個數字，有以下三種情況。
1. 這 k + 2 個數皆小於等於 2k，代表從前 2k 個數字中選出 k + 2 個數字，根據歸納假設，從前 2k 個數中選出 k + 1 個數，必存在兩個數，其中一數可以整除另外一數。因此，這 k + 2 個數中也存在兩數為倍數關係。
2. 在這 k + 2 個數中，選了一數大於 2k，而剩下 k + 1 個數字小於等於 2k。根據歸納假設，這 k + 1 個數是從前 2k 個數字中選出來的，必存在兩數，其中一數可以整除另一數。因此，這 k + 2 個數中也存在兩數為倍數關係。
3. 在這 k + 2 個數中，選了二數大於 2k，即選了 2k + 1 和 2k + 2，而剩下 k 個數字小於等於 2k。
a. 若這 k 個數當中有選 k + 1，則 (k + 1) | (2k + 2)，命題成立。
b. 若這 k 個數當中沒有選 k + 1 :
令解集合 A 收集的是選了 2k + 1 和 2k + 2 但沒有選 k + 1 的解。
現在考慮一個新的解集合 B，我們暫時地不選 2k + 2，選了 2k + 1 和 k + 1，則可以套用 Case 2，因為 2k + 1 大於 2k，且能從 1 ~ 2k 中選 k + 1 個數字，所以存在兩數 a, b 使得 a | b。如果 a 和 b 皆不等於 k + 1，則此解一定也會在 A 中，故命題成立。如果 a 或 b 等於 k + 1，假設 b = k + 1，則 a | (k + 1)，在解集合 A 中，a 一定會整除 2k + 2，因為 (k + 1) | (2k + 2)，所以 a | (2k + 2)，故命題亦成立。

因此由數學歸納法可得證。

---
### 8
> Let $d_1, d_2, ..., d_n, n\geq 2$, be positive integers. Prove that if $d_1 + d_2 + ... + d_n = 2n-2,$ then there exists a tree with $n$ vertices of degrees exactly $d_1, d_2, ..., d_n$. Based on your proof, design an efficient algorithm to construct such a tree.

Let $n=2$. We have $d_1+d_2=2$. Since $d_1, d_2$are positive integers, $d_1=d_2=1$. There exists an edge within two vertices. Therefore, the statement holds when $n=2$.

Let $n=m$, if $d_1 + d_2 + ... + d_m = 2m-2, \forall m \geq 2,$ then there exists a tree with $m$ vertices of degrees exactly $d_1, d_2, ..., d_m$.

Let $n=m+1$, we want to prove $d_1 + d_2 + ... + d_m+d_{m+1}=2(m+1)-2$. We have a sequence of positive integers $d_1, d_2, ..., d_m, d_{m+1}, m\geq 2$. When a vertex $d_{m+1}$ is added to any vertex connected by an edge, the degree increases by 2. We have

$$
\begin{align}
d_1 + d_2 + ... + d_m+d_{m+1} &= 2m-2+2 \\
&= 2(m+1)-2
\end{align}
$$

Thus, when $n=m+1$ the statement still holds.

Therefore, $\forall n \geq 2$, if $d_1 + d_2 + ... + d_n = 2n-2,$ then there exists a tree with $n$ vertices of degrees exactly $d_1, d_2, ..., d_n$.

**Algo**
定義 adj[n][n] 為儲存樹的 n * n Adjacency matrix。

Input : d1, d2, ..., dn
Output : construct a tree if there exists a tree with the given degree sequence

if d1 + d2 + … + dn = 2n - 2
    for i = 1 to n
        for j = i + 1 to n
            if(di == 0) break // 邊數已經建完後面節點就不用管了
            if(dj == 0) continue // 點 j 不能再加入邊了
            adj[i][j] = adj[j][i] = 1
            di = di - 1
            dj = dj - 1     
    return adj[][]
else return "There is no such a tree"

Time : $O(n^2)$

---
### 9
> Let $G=(V, E)$ be a directed graph (not necessarily acyclic). Design an efficient algorithm to label the vertices of the graph with distinct labels from $1$ to $|V|$ such
that the label of each vertex $v$ is greater than the label of at least one of $v$’s
predecessors, or determine that no such labeling is possible. (A predecessor of $v$ is
a vertex $w$ such that $wv \in E$.)

**想法** : 找到 indegree = 0 的點，並從該點當作起點，利用 DFS 走訪整張圖，每拜訪一個點就為該點設編號。拜訪第一個點設 1 號，拜訪第二個點設 2 號，依此類推。當發現此圖有迴圈時，則不存在此種編號方式。DFS 走訪完後，檢查每個點是否都有拜訪過，如果有點沒被拜訪過代表此圖不連通，亦不存在此種編號方式。
**時間** : O(V + E)，DFS 走訪整張圖的時間。

---
### 10
> Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect matching: a set of edges that touches each node exactly once.

**想法** : 給定一樹 T，從樹葉節點 L 開始配對，因為樹葉節點的分支度為 1，所以若要配對一定得和其父節點 P 組成一對。組好一對 (L, P) 後，將樹葉節點 L 和其父節點 P 從樹中刪除。接著再繼續找下一個樹葉節點進行上述動作，直到樹 T 為空，代表此樹有 Perfect Matching。如果過程中發現樹 T 有度數為 0 的節點代表該點已經孤立了，則此樹就不會有 Perfect Matching。

**演算法** :

定義一邊集合 M = ∅，收集每組配對 (i, j) 的邊
while |T|≠ ∅
    若 T 有一節點 L 的度數為 0，回傳 "No matching"
    否則，找一樹葉節點 L
         令 p 為 L 的鄰點
         將邊 (p, L) 加入邊集合 M
         從樹 T 中刪除節點 p 和 L (兩點的鄰邊也一同刪除)
回傳 M

**時間分析** : 一個一個刪掉樹葉節點和其鄰點，基本上就是遍歷一整棵樹，所以時間為線性時間。

---
### 11
> Consider a variation of the towers of Hanoi. We no longer assume that all the disks are initially on one peg. They may be arbitrarily distributed among the three pegs, as long as they are ordered in decreasing sizes on each peg. The purpose remains to move all disks to one specified peg, under the same constraints as the original problem, with as few moves as possible. Design an algorithm to compute the minimal number of moves. How about the reverse of the problem?

想法 : 從最大的盤子開始思考要怎麼移動到目標柱。

令三個柱子分別為 A, B, C，總共有 n 個盤子。假設第 n 個盤子位於柱子 X，目標柱為 C。

定義 f(n, target) 為變化版河內塔，將 n 個散落於三個柱子的盤子全部移動到目標柱 target 上。
定義 g(n, P, target) 為原始版河內塔，將 n 個盤子全部移動到目標柱 target 上，過程中透過柱子 P 輔助。

1. 若第 n 個盤子位於柱子 C，則不需移動，所以現在問題縮小，只需考慮移動前 n - 1 個盤子，即解 f(n-1, C)。
2. 若第 n 個盤子不在柱子 C，則要將前 n - 1 個盤子移動到不是目標柱 C 也不是柱子 X 的柱子 Y 上，此時問題縮小成將 n - 1 個盤子移到柱子 Y 上，即 f(n-1, Y)。移動完之後再將第 n 個盤子搬到柱子 C，然後剩下 n - 1 個盤子再從柱子 Y 移動到柱子C(透過X輔助)，此時問題轉為原始河內塔版本，即 g(n-1, X, C)。


---
### 12
> Let T be an undirected tree. The diameter of T is the maximal distance over all pairs of vertices. Design an algorithm to find the diameter of the given tree.

**想法:**
1. 從一個tree任意挑一個點s為起始點，用BFS走tree，找到離s最遠的點v。
2. 從v當起點，用BFS走tree，找到離v最遠的點u，$d(u,v)$為diameter of tree

**Algo:**

Input: T (a tree), s (start node)
Output: diam (diameter of T), p0 (diameter start node), p1 (diameter end node)

visited = {s}
u = s
while u.leaf ∩ visited ∉ Ø
    v = find the child of u with maximal distance d(u, v'), where v' ∈ u.leaf \ visited
    visited = visited U {v}
    u = v
p1 = u
    
diameter = 0
visited = {u}
while u.leaf ∩ visited ∉ Ø
    v = find the child of u with maximal distance d(u, v'), where v' ∈ u.leaf \ visited
    diam = diam + d(u,v)
    visited = visited U {v}
    u = v
p2 = u

**證明:**

---
### 13
> Design an algoritm to solve Problem 146 “ID Codes” in vol.1.
{%pdf https://onlinejudge.org/external/1/146.pdf %}

**想法:**

Find $x \in R(y),$ $y$ s.t. $y<x$. (x=rightmost char in $R(y)$)


Exchange x & y, $S_1$ & $S_2$ (reversed).

**Algo** :

Input: S (a string)
Output: S (string of the successor)

for i = 0 to S.length-1
    if S[i] < S[i+1]
        y = i

for i = y+1 to S.length
    if S[i] > S[y]
        x = i
        
S1 = a substring from y to x
S2 = a substring from x to S.length
Exchange S[y] and S[x]
Reverse S1, S2 and exchange S1, S2


---
### 14
> Consider the iterative method for solving the towers of Hanoi problem described in Unit 2. Prove the correctness of the algorithm.

我們假設有 $3$ 個塔 $P_0,P_1,P_2$，和 $K$ 個圓盤，$D_1,D_2,\cdots,D_K, K\in N$，並假設在一開始所有圓盤在 $P_0$ 上。

當 $K=1$ 時，將$D_1$從$P_0$移至$P_1$，演算法成立。
\
當 $K=2$ 時，將$D_1$從$P_0$移至$P_1$，並將$D_2$從$P_0$移至$P_2$，再將$D_1$從$P_1$移至$P_2$，演算法成立。
\
假設當$K=n$且$n$是奇數時，演算法成立。(可成功將$D_1,D_2,\cdots,D_K$從$P_0$移至$P_1$)。
當 $K=n+1$ 時，先將前$n$個圓盤從$P_0$移至$P_1$(根據假設成立)，再將$D_{n+1}$從$P_0$移至$P_2$，接著將前$n$個圓盤從$P_1$移至$P_2$(根據假設成立)，故演算法成立。
\
假設當$K=n$且$n$是偶數時，演算法成立。(可成功將$D_1,D_2,\cdots,D_K$從$P_0$移至$P_2$)。
當 $K=n+1$ 時，先將前$n$個圓盤從$P_0$移至$P_2$(根據假設成立)，再將$D_{n+1}$從$P_0$移至$P_1$，接著將前$n$個圓盤從$P_2$移至$P_1$(根據假設成立)，故演算法成立。