---
# System prepended metadata

title: 演算法設計作業

---

演算法設計作業
===

### 1. 利用你的電腦執行insertion sort以及quick sort。試著繪出line plot圖比較兩者在時間($T$)/數量($N$)的差異。
![](https://i.imgur.com/X9rElfw.png)

---
### 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$)
>&ensp;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
>&ensp;Choose $u \in V-S$, so that $L(u)$ is the smallest;
>&ensp;$S=S \bigcup \{u\};$
>&ensp;for all $j$ in $V-S$ and $\exists(u,j)$
>&ensp;&ensp;$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 &ensp;(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)$ &ensp;($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)$ &ensp;(用Dijkstra's algorithm)
>2.$O(mn^2)$ &ensp;(找到mn個Cycle並計算權重)
>3.$O(mnlog(mn))$ &ensp;(排序mn個Cycle)
>4,$O(mn*k*m)=O(m^3n)$ &ensp;
>(每個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.
![](https://i.imgur.com/ZHfkvh0.png)



---
### 12. Consider the following graph. Find the shortest route from S to T by the ++dynamic programming++ approach.
![](https://i.imgur.com/WHT2H5n.png)

採用==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++.
![](https://i.imgur.com/DJUqfMf.png)

$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$
![](https://i.imgur.com/BfcRqlD.png)




#### \(c\) (Balanced parentheses) Find all balanced parentheses for $n=4$.

$C_4 = \frac{1}{5}·\binom{8}{4}=\frac{1}{5}·70 =14$
|$(((())))$|$((()()))$|$(()()())$|$((())())$|$(()(()))$|
|----------|----------|----------|----------|----------|
|$()()()()$|$(())()()$|$()(())()$|$()()(())$|$((()))()$|
|$()((()))$|$()(()())$|$(()())()$|$(())(())$|          |






