演算法設計作業
===
### 1. 利用你的電腦執行insertion sort以及quick sort。試著繪出line plot圖比較兩者在時間($T$)/數量($N$)的差異。
---
### 2. Cayley's Formula：由$n$個點所構成的擴張樹共有$n^{n-2}$種可能。請用中文描述証明的詳細過程。
:::success
Cayley's formula :There are $n^{n−2}$ different labeled trees on n vertices.
:::
:::info
Prüfer sequence:A tree graph G on n labelled vertices, we can find a sequence of G contains n-2 entries of {1,2,...,n} labelled vertices that is unique to G
:::
>Prüfer sequence演算法：
A labelled Graph G with vertices{1,2,...,n}, |G|=n
Step1 移除label最小的leaf，將該leaf的parent加到序列S
Step2 重複Step1直到剩下兩個頂點
在圖Ｇ有n個頂點，Prüfer sequence可以找到一個序列有n-2個{1,...,n}中標記的頂點，該序列能找到一個唯一的生成樹。
用Prüfer可以簡單的證明Cayley's formula，每個不同組合的序列可以找到唯一個生成樹，序列中每個元素有n種可能，依乘法原理，會有$n^{n-2}$個生成樹
---
### 3. 求Median Finding Algorithm的時間複雜度。
Median of Medain algorithm:
A Array $A$ that $|A|=n$, want to find $k$th-smallest/biggest number
>Median of Medain(A,k)
>Step1:
>Devided Array $A$ into sublist that each lengh is 5(if fewer than 5 element, it's fine)
>
>Step2:
>Sort each sublist and find its median, put these medians in a list and find the median $p$
>(Sort small sublist cost $O(n)$)
>
>Step3:
>Let $S_1=\{x \in A,x<p \}$
>$S_2=\{x \in A,x=p \}$
>$S_3=\{x \in A,x>p \}$
>if $|S_1| < k$, then Median of Medain($S_1$,$k$)
>else if $|S_1|+|S_2| \le k$, $p$ is $k$th-smallest/biggest number of A
>else $k' = k-(|S_1|+|S_2|)$, then Median of Medain($S_3$,$k'$)
Time complexity:$O(n)$
$T(n)=T(\frac{n}{5})+T(\frac{7n}{10})+O(n) = O(n)$
---
### 4. 求找出陣列中第$k$大的數的時間複雜度。
用第3題的做法，所以時間複雜度是$O(n)$
---
### 5. 求找出陣列中最大及最小數的時間複雜度。
用第3題的做法，所以時間複雜度是$O(n)$
---
### 6. 求最小擴張樹的Kruskal’s algorithm的時間複雜度。
A weighted connected undircted graph $G=(V,E)$
Algorithm:
>Step1:
>Sort all edges
>
>Step2:
>Add the smallest weight edge to the forest if it will not cause a cycle
>
>Step3:
>Stop if n-1 edges. Otherwise, go to Step2
Time complexity:$O(|E|log|E|)$
>1.Sort:$O(|E|log|E|)$
>
>2.Make set:$|V|$
>Find set:$2|E|$
>Union:$O(1)$
>
>$T(n)=O(|E|log|E|)+O(E)=O(|E|log|E|)$
---
### 7. 求最小擴張樹的Prim’s algorithm的時間複雜度。
A weighted connected undircted graph $G=(V,E)$
Algorithm:
>Step1:
>$x\in V$, Let $A=\{x\}, B=V-\{x\}$
>
>Step2:
>Select $(u,v) \in E, u \in A,v \in B, \exists(u,v)$ has the smallest weight between A and B
>
>Step3:
>$(u,v)$ is in the tree, $A=A\bigcup\{v\}, B=B-\{v\}$
>
>Step4:
>If $B= \emptyset$, stop; Otherwise, go to Step2
Time complexity:$O(n^2)$
>Every time check $v$ in $B$ can be added to $A$, that is $O(|V|)$ times, and we must repeat the checking process at |V| times, so the runnung time is $O(|V|^2)$
---
### 8. 求單一起點最短路徑的Dijkstras’s algorithm的時間複雜度。
A weight directed graph $G=(V,E)$, A set $S \subseteq V$ denotes the shortest path
Algorithm:
>Step1:
>$S=\{v_0\}$
>
>Step2:
>for $i=1$ to $n$ do ($|V|=n+1$)
> if $(v_0,v_i) \in E$, then $L(v_i)=w(v_0,v_i)$, else $L(v_i)=\infty;$
>
>Step3:
>for $i=1$ to $n$ do
> Choose $u \in V-S$, so that $L(u)$ is the smallest;
> $S=S \bigcup \{u\};$
> for all $j$ in $V-S$ and $\exists(u,j)$
>  $L(j)=min\{L(j), L(u)+w(u,j)\}$
Time complexity:$O(n^2)$
>every time calculate $L(j)$ cost $O(n)$ times, and repeat $n$ times, so time complexity is $O(n^2)$
---
### 9. 求2-way merging problem的時間複雜度。
input $k$ sorted lists, get an optimal 2-way merge tree
Algorithm:
>Step1:
>Generate $k$ trees, each tree has a node with weight $n_i$(the length of the list), sort k weights  (cost $O(nlogn)$)
>
>Step2:
>Choose two trees $T_1$ and $T_2$ with minimun weights
>
>Step3:
>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$
>
>Step4:
>Replace $T_1$ and $T_2$ by $T$
>
>Step5:
>Stop if only one tree left, else go to step2
Time complexity:$O(nlogn)$
>1.$O(nlogn)$
>2.$O(1)$
>3.$O(1)$
>4.$O(logn)$
>5.$O(n)$
$T(n)=O(nlogn)+O(1)+O(1)+O(logn)+O(n)=O(nlogn)$
---
### 10. 求minimal cycle basis problem的時間複雜度。
A weight directed graph $G=(V,E)$
Algorithm:
>Step1:
>找到每對頂點的最短路徑 (用Dijkstra's algorithm)
>
>Step2:
>每個頂點$v \in V$與每個邊$(x,y) \in E$在$G$中組成Cycle $C(x,y,z)=P(v,x)+P(v,y)+P(x,y)$  ($P(a,b)$為$(a,b)$的最短路徑)
>
>Step3:
>依權重排序$C$
>
>Step4:
>從$C$中找出$MCB$(minimal cycle basis)
Time complexity:$O(m^3n)$
>$n=|V|,m=|E|,k=m-n+1$(size of basis)
>1.$O(n^3)$  (用Dijkstra's algorithm)
>2.$O(mn^2)$  (找到mn個Cycle並計算權重)
>3.$O(mnlog(mn))$  (排序mn個Cycle)
>4,$O(mn*k*m)=O(m^3n)$  
>(每個Cycle與邊的關係矩陣如:$C_1=[1,1,1,0,0,0,0]$，與其他Cycle做$XOR$找出最小矩陣，$m$個邊、$k$個cycle basis，每個$C$做$O(mk)$次，有$mn$個Cycle，所以共做$O(mn*k*m)$次)
>
>$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.
採用==backward reasoning==的方法，尋找$S$到$Ｔ$的最短路徑
- $\ d(S,T)=min\{4+d(A,T), 5+d(B,T), 1+d(C,T)\}$
我們需要找到各點至T的最短路徑，像是做遞迴一樣
- $\ d(A,T)=min\{10+d(D,T),9+d(F,T)\}$
- $\ d(D,T)=4$
- $\ d(F,T)=5$
- $\ d(B,T)=min\{6+d(D,T), 5+d(E,T)\}$
- $\ d(D,T)=4$
- $\ d(E,T)=3$
- $\ d(C,T)=min\{11+d(E,T), 2+d(G,T)\}$
- $\ d(E,T)=3$
- $\ d(G,T)=3$
把數值帶進去
- $\ d(A,T)=min\{14,14\}=14$
- $\ d(B,T)=min\{10,8\}=8$
- $\ d(C,T)=min\{14,5\}=5$
- $\ d(S,T)=min\{18,13,6\}=6$
最短路徑為：$S \rightarrow C \rightarrow G \rightarrow T$
---
### 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?
使用==branch-and-bound==得到的圖
```graphviz
digraph G{
node[shape = circle];
splines=false;
n1 [label = D]
n2 [label = D]
n3 [label = E]
n4 [label = E]
{
S->A [label = "4"]
S->B [label = "5"]
S->C [label = "1"]
C->n3 [label = "11"]
C->G [label = "2"]
G->T [label = "3"]
A->n1 [label = "10"]
A->F [label = "9"]
B->n2 [label = "6"]
B->n4 [label = "5"]
}
}
```
Dynamic programming的方式需要跑完整張圖，但Branch-and-Bound只會跑完部分圖，以Fig7.1來看，==Branch-and-Bound==的方法會比較快
---
### 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 G{
rankdir = LR;
//splines=false;
node[shape = circle, fontsize = 10];
ranksep = 2.5;
nodesep = 0;
node[group = "A"]{"(0,1)" "(0,2)" }
node[group = "B"]{"(1,1)" "(1,2)" }
node[group = "C"]{S "(2,1)" "(2,2)" "(4,3)"}
node[group = "D"]{"(3,1)" "(3,2)" }
node[group = "E"]{"(4,1)" "(4,2)" }
{
S->"(0,1)" [label = "0"]
S->"(1,1)" [label = "3"]
S->"(2,1)" [label = "7"]
S->"(3,1)" [label = "10"]
S->"(4,1)" [label = "12"]
"(0,1)"->"(0,2)" [label = "0"]
"(0,1)"->"(1,2)" [label = "1"]
"(0,1)"->"(2,2)" [label = "2"]
"(0,1)"->"(3,2)" [label = "6"]
"(0,1)"->"(4,2)" [label = "9"]
"(0,2)"->"(4,3)" [label = "9"]
"(1,1)"->"(1,2)" [label = "0"]
"(1,1)"->"(2,2)" [label = "1"]
"(1,1)"->"(3,2)" [label = "2"]
"(1,1)"->"(4,2)" [label = "6"]
"(1,2)"->"(4,3)" [label = "8"]
"(2,1)"->"(2,2)" [label = "0"]
"(2,1)"->"(3,2)" [label = "1"]
"(2,1)"->"(4,2)" [label = "2"]
"(2,2)"->"(4,3)" [label = "4"]
"(3,1)"->"(3,2)" [label = "0"]
"(3,1)"->"(4,2)" [label = "1"]
"(3,2)"->"(4,3)" [label = "2"]
"(4,1)"->"(4,2)" [label = "0"]
"(4,2)"->"(4,3)" [label = "0"]
{rank = same;}
}
}
```
找出總最大利益：
$S \rightarrow (3,1) \rightarrow (3,2) \rightarrow (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|==1==|1|1|1|1|1|1|1|
|d|0|1|1|1|1|==2==|2|2|2|
|f|0|1|1|1|1|2|2|2|==3==|
$LCS(S_1,S_2) = adf$
---
### 16. (Catalan 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$.
[1 2 3 4] $\rightarrow$ [? ? ? ?]
$C_4 = \frac{1}{5}·\binom{8}{4} = \frac{1}{5}·70=14$
[4 3 2 1]
[3 2 1 4] [4 2 1 3] [4 3 1 2]
[2 1 3 4] [2 1 4 3] [3 1 2 4] [4 1 2 3] [4 1 3 2]
[1 2 3 4] [1 2 4 3] [1 3 2 4] [1 4 2 3] [1 4 3 2]
#### (b) (Binary search tree) Find all possible binary search tree for $n=4$.
$C_4 = \frac{1}{5}·\binom{8}{4}=\frac{1}{5}·70 =14$
#### \(c\) (Balanced parentheses) Find all balanced parentheses for $n=4$.
$C_4 = \frac{1}{5}·\binom{8}{4}=\frac{1}{5}·70 =14$
|$(((())))$|$((()()))$|$(()()())$|$((())())$|$(()(()))$|
|----------|----------|----------|----------|----------|
|$()()()()$|$(())()()$|$()(())()$|$()()(())$|$((()))()$|
|$()((()))$|$()(()())$|$(()())()$|$(())(())$| |
Sign in with Wallet
Connect another wallet