# Homework

## Lists

- [HW-1](https://hackmd.io/@ysl/SkcJ3mJXp/edit)
- [HW-2](https://hackmd.io/@ysl/SyIsnXyXT/edit)
- [HW-3](https://hackmd.io/@ysl/HyT9nXyQa/edit)
- [HW-4](https://hackmd.io/@ysl/S1Qi3Xkma/edit)
- [HW-5](https://hackmd.io/@ysl/HyEepQy7a/edit)
- [HW-6](https://hackmd.io/@ysl/rkceamkXp/edit)
- [HW-7](https://hackmd.io/@_EUdnTNeRl-LUa2kz_WvLw/SkrBcugv6)

## HW-1 (Legacy)
### 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時命題亦成立，故由數學歸納法可得證。