# 台大 103 軟體
###### tags: `NTU` `103` `軟體`
1. (a) O(lgnlglgn) (b) O(n) \(c\) O(lgn)
2. (a) $\binom{k}{i}$
:::info
用數學歸納法證
在 k = 0 時，$\binom{0}{0} = 1$
假設在 k = n - 1 時，命題成立
則 $B_k$ 深度為 i 的點數量 = $\binom{k-1}{i}+\binom{k-1}{i-1}=\binom{k}{i}$
:::
(b) lgn
:::info
假設深度為 k，則根據 (a)，$\sum_{i=0}^{k} \binom{k}{i}=2^k=n$，得 $k=lgn$

樹中的每一個點都是某個 $B_i$ 的根，$i\le k$，而根的 degree 為 $\binom{i}{0}$，因此 degree 最大即為 $\binom{k}{0}=k=lgn$
:::

3.
(a) 令 $G'= (V\cup\{c\}, E\cup \{\{a,c\},\{b,c\}\})$。若 $G'$ 有 Hamilton Cycle $C$，則 $C$ 必包含 $\{a,c\}$ 與 $\{b,c\}$，將這兩條邊拿掉，即為 given endpoint hamilton path。因此，若 hamilton cycle problem 具備多項式時間解，則 given endpoint hamilton path 即可利用上述轉換在多項式時間內求解。但 given endpoint hamilton path 已知為 NPC，因此 hamilton cycle problem 必為 NPC

(b) 令 $G'=(V,E'),\ E'=\{\{a,b\}|\ \forall a,b\in V\}$。$c(a,b)=0$ if $\{a,b\}\in E$, $c(a,b)=1$ if f$\{a,b\}\notin E$。對 $G'$ 求 bound = 0 的 TSP 解，所得即為 hamilton cycle。

\(c\) degree = 2 的 bounded degree spanning tree problem 即為 any endpoint hamilton path problem

4. 利用 Dijkstra 計算最短路徑時，需要考量的東西，除了「點」本身外，還得考量通過了多少條 thick edge、多少條 thin edge。因此很容易想出以下擴展：令 $d[v_i][a][b]$ 為 $A$ 到 $v_i$、通過 a 條 thick edge、b 條 thin edge 的最短路徑。對於任意 $v_i,v_j$，在 relax $e=\{v_i,v_j\}$ 時，若 $e$ 為 thick edge，則要更新的狀態是 $d[v_j][a+1][b]$，反之則為 $d[v_j][a][b+1]$。所求即為 $d[F][k][n]$
5. 楓葉本裡有，我就懶。