# 演算法設計作業(NCUE)
### 1. 利用你的電腦執行insertion sort以及quick sort。試著繪出line plot圖比較兩者在時間(T)/數量(N)的差異。
---
### 2. Cayley's Formula：由$n$個點所構成的擴張樹共有$n^{n-2}$種可能。請用中文描述証明的詳細過程。
$Cayley’s Formula$
$\qquad$$|T_n |=n^{n-2}$ (※)
Proof :
令$A$為從$n$個頂點中任意取$k$個頂點的集合($A$集合有$k$個元素)，定義 $T_{(n,k)}$ 為$n$個頂點上的所有森林的集合，且這些森林有$k$個樹，使得$A$的每個頂點都在不同的樹中。
$A={1,2,…,k}$，頂點1可以與剩餘的$n-k$個頂點中的$i$個相鄰，且$i$的範圍可以從0到$n-k$。若刪除頂點1，則得到$k-1+i$個頂點，且分布於不同的樹中，將所有$i$的樹的數量相加，得到 $T_{n,k}$。
$\qquad$$\qquad$$\qquad$$\qquad$$T_{n,k}$ = $\displaystyle\sum_{k=0}^{n}\left(
\begin{array}{ccc}n-k \\i \\\end{array}\right)T_{n-1,(k-1)+i}$ ($*$)
因為可以從$n-k$個頂點中選擇i個頂點。
Note : $T_{0,0}$ = 1 , $T_{n,0}$ = 0 for $n$ > 0 , so that $T_{n,n}$ = 1
Proposition : 我們有
$\qquad$$\qquad$$\qquad$$T_{n,k}$ = $kn^{n-k-1}$
$\qquad$$\qquad$$\qquad$$T_{n,1}$ = $T_n$ = $n^{n-2}$
使用前述等式($*$)並使用數學歸納法
$T_{n,k}$ = $\displaystyle\sum_{i=0}^{n-k}\left(
\begin{array}{ccc}n-k \\i \\\end{array}\right)T_{n-1,(k-1)+i}$
$\qquad$ = $\displaystyle\sum_{i=0}^{n-k}\left(
\begin{array}{ccc}n-k \\i \\\end{array}\right)(k-1+i)(n-1)^{(n-1)-(k-1+i)-1}$
令 $i = n-k-i$
$\qquad$ = $\displaystyle\sum_{i=0}^{n-k}\left(
\begin{array}{ccc}n-k \\i \\\end{array}\right)(k-1+i)(n-1)^{i-1}$
$\qquad$ = $\displaystyle\sum_{i=0}^{n-k}\left(
\begin{array}{ccc}n-k \\i \\\end{array}\right)(n-1)^i-\displaystyle\sum_{i=1}^{n-k}\left(
\begin{array}{ccc}n-k \\i \\\end{array}\right)i(n-1)^{i-1}$
$\qquad$ = $n^{n-k}-(n-k)$$\displaystyle\sum_{i=1}^{n-k}\left(\begin{array}{ccc}n-1-k \\i \\\end{array}\right)i(n-1)^{i-1}$
$\qquad$ = $n^{n-k}-(n-k)$$\displaystyle\sum_{i=1}^{n-1-k}\left(\begin{array}{ccc}n-1-k \\i \\\end{array}\right)(n-1)^{i}$
$\qquad$ = $n^{n-k}-(n-k) n^{n-1-k}=kn^{n-1-k}$
$∴T_{(n,k)}=kn^{n-k-1}$
所以$T_n=T_{n,1}$ $=n^{n-2}$ (※)證明$Cayley’s formula$。
---
### 3. 求Median Finding Algorithm的時間複雜度。
median-of-medians$(A,i)$，設$A$中元素都不相同
step1.將list分為多個長度為5的sublist。
step2.對所有sublist排序並找出其中位數。
step3.使用median-of-medians algorithm遞迴去決定出所有中位數集合中的中位數。
step4.使用此中位數作為pivot元素(記作$x$)。
step5.重新排序$A$陣列，使得在$A$中，比$x$小的元素放在$x$的左邊；比$x$大的元素放在$x$的右邊。
step6.令$k$表示$x$的rank，即對於$S$的數目集合，$x$是$S$中第$k$個最小的數
step7.
$\quad$a. if $i=k$ ,return $x$
$\quad$b. if $i<k$ ,then recurse using median-of medians on $(A[1, ..., k-1],i)$
$\quad$c. if $i>k$ ,then recurse using median-of medians on $(A[k+1, ..., i],i-k)$
#### Time complexity : <font color="#0991E6">$O(n)$</font>
$T(n)=T(\dfrac{n}{5})+T(\dfrac{7n}{10})+O(n)$
---
### 4. 求找出陣列中第$k$大的數的時間複雜度。
使用第三題的方法
若$A$陣列有$n$個元素，則使用medians-of-median algorithm
尋找$A$中第$n-k$小的元素，就是$A$中第k大的元素
因此時間複雜度同樣為<font color="#0991E6">$O(n)$</font>
---
### 5. 求找出陣列中最大及最小數的時間複雜度。
使用第三題的方法，因此時間複雜度同樣為<font color="#0991E6">$O(n)$</font>
---
### 6. 求最小擴張樹的Kruskal’s algorithm的時間複雜度。
Step1.依照weight大小，排序edges ($O(|E|log|E|)$)
Step2.從最小edge加入正在構建的圖，但不能形成cycle ($|V|-1$ times)
Step3.直到剩下$n-1$個edges，否則重複Step2 (2$|E|$ times)
#### Algorithm :
Input:A weighted, connected and undirected gragh $G=(V,E)$
Output:$T ≔ Ø$
$\quad$$\qquad$While $T$ contains less than $n-1$ edges do
$\quad$$\qquad$Begin
$\quad$$\qquad$$\quad$Choose edge$(v,w)$ from $E$ of the smallest weight
$\quad$$\qquad$$\quad$Delete $(v,w)$ from $E$
$\quad$$\qquad$$\quad$If (the adding of $(v,w)$ to $T$ does not create a cycle in $T$)
$\quad$$\qquad$$\quad$then add $(v,w)$ to $T$
$\quad$$\qquad$$\quad$Else
$\quad$$\qquad$$\qquad$Discard$(v,w)$
$\quad$$\qquad$End
#### Time complexity : <font color="#0991E6">$O(|E|log|E|)$</font>
---
### 7. 求最小擴張樹的Prim’s algorithm的時間複雜度。
Step1. Let $x$ be any vertex in $V$. $X$={$x$} and $Y$=$V$-{$x$}
Step2. Select an edge ($u$,$v$) from E, such that $u∈X$, $v∈Y$
$\qquad$$\quad$and ($u$,$v$) has the smallest weight among edges between $X$ and $Y$
Step3. Connect $u$ to $v$. $X$=$X$∪{$V$} and $Y$=$Y$$-${$V$}
Step4. If $Y=Ø$, then the resulting tree is a minimum spanningtree.
$\qquad$$\quad$Otherwise, go to Step2.
#### Time complexity : <font color="#0991E6">$O(|V|^2)$</font>
每一次檢查$Y$中的頂點是否加入$X$ ( $O|V|$ time )
且需重複檢查的此過程 ( $|V|$ times )
---
### 8. 求單一起點最短路徑的Dijkstras’s algorithm的時間複雜度。
#### Algorithm :
Input:A directed graph $G(V,E)$ and a vertex $v_0$. For all $(u,v)∈E$
Output:$S:={v_0}$
For $i=1$ to $n$ do
If $(v_0,v_i)∈E$, then $L(v_i)=cost(v_0,v_i)$
Else $L(v_i)=∞$
For $i=1$ to $n$ do
choose $u$ from $V-S$ such that $L(u)$ is smallest
$S=S$$\,$$∪$$\,${$u$}
for all $w$ in $V-S$ do
$L(w)=min$$\,${$\,$$L(w)$, $L(u)+cost(u,w)$$\,$}
#### Time complexity : <font color="#0991E6">$O(V^2)$</font>
For all vertex $V$, need to relax connected edges, order to find minimum cost edge, need $V$ numbers of calculation and every operation need $O(V)$ times.
Hence time complexity is $O(V^2)$
---
### 9. 求2-way merging problem的時間複雜度。
#### Algorithm :
Input: $k$ sorted lists
Output: an optimal 2-way merge tree
Method:
Step 1: Generate $k$ trees, each tree has a node with weight $n_i$ (the length of the list); (sorted $k$ weights)
Step 2: Choose two trees $T_1$ and $T_2$ with minimum weights;
Step 3: Create a new tree $T$ whose root has $T_1$ and $T_2$ as its subtree,
and the weight of $T$ is the sum of weights of $T_1$ and $T_2$;
Step 4: Replace $T_1$ and $T_2$ by $T$;
Step 5: If there is only one tree left then stop; else go to Step 2.
#### Time complexity : <font color="#0991E6">$O(nlogn)$</font>
$T(n)=T(nlogn)+T(1)+T(1)+T(logn)+T(n)=O(nlogn)$
---
### 10. 求minimal cycle basis problem的時間複雜度。
#### Algorithm :
Input: A weight directed graph $G=(V,E)$
Step1. Find the shortest path for each pair of vertices(use Dijkstra's algorithm)
Step2. For each vertex $v∈V$ and every edge $(x,y)∈E$ form a cycle in $G$
$C(x,y,z)=P(v,x)+P(v,y)+P(x,y)\quad(P(a,b)$ is the shortest path for $(a,b))$
Step3. Sort $C$ by weight
Step4. Find $MCB(minimal cycle basis)$ from $C$
#### Time complexity : <font color="#0991E6">$O(m^3n)$</font>
$n=|V|,m=|E|,k=m-n+1$ (size of basis)
$\qquad$step1. use Dijkstra's algorithm $→O(n^3)$
$\qquad$step2. Find $mn$ cycles and calculate the weight $→O(mn^2)$
$\qquad$step3. Sort these $mn$ cycles $→O(mnlog(mn))$
$\qquad$step4. $O(mn\cdot k\cdot m)=O(m^3n)$
$T(n)=O(n^3)+O(mn^2)+O(mnlog(mn)+O(m^3n))=O(m^3n)$
---
### 11. Solving the 8-puzzle problem by using A algorithm. The staring node is positioned as shown in Fig. 5.14.
---
### 12. Consider the following graph. Find the shortest route from S to T by the dynamic programming approach.
使用<font color="#38AD55">$backward\ reasoning$</font>，找出S到T的最短路徑
$d(S,T)$ $=min$ { $4+d(A,T)\ ,5+d(B,T) ,1+d(C,T)$ }
$d(A,T)$ $=min$ { $10+d(D,T)\ ,9+d(F,T)$ } $=min$ { $10+4\ ,9+5$ } $=14$
$d(B,T)$ $=min$ { $(6+d(D,T)\ ,5+d(E,T)$ } $=min$ { $6+4\ ,5+3$ } $=8$
$d(C,T)$ $=min$ { $11+d(E,T)\ ,2+d(G,T)$ } $=min$ { $11+3\ ,2+3$ } $=5$
將得到的值帶回 $d(S,T)$
$d(S,T)$ $=min$ { $4+14 ,5+8\ ,1+5$ } $=6$
∴the shortest path is : $S→C→G→T\ :\ 1+2+3=6.$
---
### 13. For the graph shown in Fig. 7.1, solve the same problem by using the branch-and-bound approach. For this problem, which approach (dynamic programming versus branch-and-bound) is better? Why?
<font size=5>**Fig. 7.1**</font>
使用<font color="#38AD55">$Branch-and-Bound$</font> 進行繪圖
```graphviz
digraph branch_and_bound{
rankdir=TB;
node [shape = circle];
S->A [label="4"]
S->B [label="5"]
S->C [label="1"]
d1 [label="D"]
A->d1 [label="10"]
A->F [label="9"]
d2 [label="D"]
B->d2 [label="6"]
e1 [label="E"]
B->e1 [label="5"]
e2 [label="E"]
C->e2 [label="11"]
C->G [label="2"]
G->T [label="3"]
}
```
Branch-and-Bound的方法只需要跑出部分圖
但是Dynamic programming卻需要跑出完整的圖
所以對於Fig. 7.1而言，使用<font color="#38AD55">$Branch-and-Bound$</font>的效率會更好。
---
### 14. For the following table, find an optimal allocation of resources to maximize the total profit for those three projects and four resources.
$P(i,j)=i\ 個\ resource\ 分給\ 1,2,...,j\ 個\ project$
```graphviz
digraph total_profit {
rankdir=LR;
ranksep=3.5
nodesep=0.08;
node [shape = circle;height=1,fontsize=25];
//利用group使圖整齊
node [group="g0"]{"(0,1)""(0,2)"}
node [group="g1"]{"(1,1)""(1,2)"}
node [group="g2"]{"S""(2,1)""(2,2)""(4,3)"}
node [group="g3"]{"(3,1)""(3,2)"}
node [group="g4"]{"(4,1)""(4,2)"}
S-> {"(0,1)"} [label="0",fontsize=25];
S-> {"(1,1)"} [label="3",fontsize=25];
S-> {"(2,1)"} [label="7",fontsize=25];
S-> {"(3,1)"} [label="10",fontsize=25];
S-> {"(4,1)"} [label="12",fontsize=25];
{"(0,1)"}-> {"(0,2)"} [label="0",fontsize=25];
{"(0,1)"}-> {"(1,2)"} [label="1",fontsize=25];
{"(0,1)"}-> {"(2,2)"} [label="2",fontsize=25];
{"(0,1)"}-> {"(3,2)"} [label="6",fontsize=25];
{"(0,1)"}-> {"(4,2)"} [label="9",fontsize=25];
{"(1,1)"}-> {"(1,2)"} [label="0",fontsize=25];
{"(1,1)"}-> {"(2,2)"} [label="1",fontsize=25];
{"(1,1)"}-> {"(3,2)"} [label="2",fontsize=25];
{"(1,1)"}-> {"(4,2)"} [label="6",fontsize=25];
{"(2,1)"}-> {"(2,2)"} [label="0",fontsize=25];
{"(2,1)"}-> {"(3,2)"} [label="1",fontsize=25];
{"(2,1)"}-> {"(4,2)"} [label="2",fontsize=25];
{"(3,1)"}-> {"(3,2)"} [label="0",fontsize=25];
{"(3,1)"}-> {"(4,2)"} [label="1",fontsize=25];
{"(4,1)"}-> {"(4,2)"} [label="0",fontsize=25];
{"(0,2)"}-> {"(4,3)"} [label="9",fontsize=25];
{"(1,2)"}-> {"(4,3)"} [label="8",fontsize=25];
{"(2,2)"}-> {"(4,3)"} [label="4",fontsize=25];
{"(3,2)"}-> {"(4,3)"} [label="2",fontsize=25];
{"(4,2)"}-> {"(4,3)"} [label="0",fontsize=25];
}
```
Total maximize profit：$S→(3,1)→(3,2)→(4,3)$
$10+0+2=12$
---
### 15. Find a longest common subsequence of $S_1=aabcdaef$ and $S_2=beadf$.
| | | a | a | b | c | d | a | e | f |
| --- | --- |:---:| --- | --- | --- | --- | --- | --- | --- |
| b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| e | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| a | 0 | ==<font color="#0991E6">1</font>== | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| d | 0 | 1 | 1 | 1 | 1 | ==<font color="#0991E6">2</font>== | 2 | 2 | 2 |
| f | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | ==<font color="#0991E6">3</font>== |
$LCS(S_1,S_2)=adf$
---
### 16. (Catalab Number) $C_n=C^{2n}_{n}-C^{2n}_{n+1}=\frac{1}{n+1}C^{2n}_{n}$.
#### (a). (Train problem) Find all possible order for $n=4$.
$C_4=C^8_4-C^8_5=$ ${1\over 5}\cdot C^8_4$ = ${1\over 5}\cdot 70 = 14$
當$n=4$時，有14種可能
1234,1243,1324,1423,1432
2134,2143,3214,3124,4123
4312,4321,4213,4132
#### (b). (Binary search tree) Find all possible binary search tree for $n=4$.
$C_4=C^8_4-C^8_5=$ ${1\over 5}\cdot C^8_4$ = ${1\over 5}\cdot 70 = 14$
#### (c\). Balanced parentheses) Find all balanced parentheses for $n=4$.
$C_4=C^8_4-C^8_5=$ ${1\over 5}\cdot C^8_4$ = ${1\over 5}\cdot 70 = 14$
| $(((())))$ | $((()()))$ |$(()()())$ |$((())())$|$(()(()))$|
| -------- | -------- | -------- |-------- |-------- |
|$()()()()$ | $(())()()$ |$()(())()$|$()()(())$|$((()))()$|
|$()((()))$|$()(()())$|$(()())()$|$(())(())$|
Sign in with Wallet
Connect another wallet