# 數學公式



>* **$(log n)!$** is <font color="#f00">not</font> polynomially bounded
>* **$(log log n)!$** is polynomially bounded



---
# Time Complexity

## Decision Tree

- Decision Tree 是 full binary tree
- 在 Comparison based 的 sorting 裡，Decision Tree 裡所有的 leaves 代表的是 $n!$ 種大小排列的可能性

> 例如 sort 三個 element，假設全部 element 大小都不同，則有長方形的那六種（$3!$）可能

- 因為從 root 到任何一個 leaf 的 path 長就是比較的次數，所以 Worst Case 就是剛好比到 tree height 次，所以 Comparison based sorting time 至少會是 $nlogn$
> 因為<font color="red">高度為 $h$ 的 binary tree 最多只有 $2^h$ 個 leaves</font>
> 並且 $n! \le l$, $\quad l: \ \#leaves$
>> 因為所有的大小排列的可能性（見上一點）都要出現在 leaves 中
>>
> 因此 $n! \le l \le 2^h$
> 同取 lg
> $\rightarrow$ $lg(n!) \le lg(2^h)$
> $\rightarrow$ $h \ge nlgn$
> 所以，Comparison based sorting 至少需要 $nlgn$ 次比較

- merge sort, heap sort 是 asymptotically optimal comparison sorts

## Time Complexity 計算：

### 是非題

### 各種型 "*" 的計算

- 由 e 選項：n 開 loglogn 次根號會變成常數，可解下方 Recursion 第 j 小題

### Recursion





## 一些 Algo / Data Structure 的 Time Complexity：



[Fibonacci heap 筆記](https://hackmd.io/0CHw0lMfT9qKEM3JYEqTjg)


> 如果 array 中<font color = "red">所有 elements 都相同</font>， quick sort 的 time 等同 worst case time = $\theta (n^2)$ （因為每次 partition 都會 return $n-1$）


- 如果要讓 quick sort stable，我們可以把每個 element 都存兩個 key，一個 key 存原來的值，一個存 index，如果比到原本的值相同，就再去比 index 的 key


- bottom up 建 Heap：$O(n)$
- top down 建 Heap：$O(nlogn)$
> 先把 heap 大小加 1，把最後一個 element 值設成負無窮大，再用 increase-key 向上挑戰父點。
> 因為每次 increase-key time = $O(logn)$，共 insert n 個點，所以 time = $O(nlogn)$

* 題目要求 store key into heap in order 須用 top-down

---
# 各種 Data Structure 及應用

## pointer


## array

- array 可以拿來 implement ++任何++ data structure，包含 user define structure

## stack / queue

### 用 stack 做 queue

用兩個 Stack S, T

- ==``enqueue()``== 直接 push
- ==``dequeue()``== 只有<font color = "green"> T 空</font>的時候才需要把 S 所有的 element ``pop()`` 出來再 push 到 T，最後再 ``pop(T)`` 所以 <font color = "red">``dequeue()`` amortized cost $= \theta(1)$</font>

### in / pre / postfix

#### infix 轉 postfix

用 stack， stack 放 <font color = "green">operator</font>

方法：
- 是 operand 就 print
- operator 的話比大小
- 如果掃到的 operator 比 stack top 大就 push
- 否則（operator 比 stack top 小）
就 pop 到掃到的 operator 比較大再 push


例子：


#### postfix 求值

stack 放 <font color = "green">operand</font>，看到 operator 就把對應數量的 operand pop 出來做運算
> 例如遇到 opertor 是 +，就 pop 兩個 operand 出來做運算

- <font color = "red">注意：先 pop 的放後面！</font>
> 例如 stack top 是 ``b``，第二個是 ``a``，遇到 operator - 時，先 pop 得到 ``b`` 再 pop 得到 ``a``，所以得到的式子是 ``a - b`` 而非 ``b - a``

---
# Dynamic Programming

## Matrix Chain

關於 Matrix Chain 的詳細說明可參考筆記：[Matrix chain multiplication](/LFXCTjLzQiy67X3x5Ex4Ag)

> 110 台

- 並非所有 DP 的問題 time 的是 $\theta(P)$ $P$：子問題個數
$\rightarrow$ 反例如 matrix chain，子問題個數為 $O(n^2)$，但時間為 $O(n^3)$



## LCS

> 計算共有比中幾個字元的 array ``c[0..m,0..n]`` 從零開始（多加一行一列，且這行這列每格初值皆填 $0$）
> 其餘++一列一列填，由左到右++
> - 如果比中：箭頭指向左上，值是左上值 $+1$
> - 如果沒比中：看左邊、上面哪格值較大，箭頭指向值大的那格，值和選擇的那格相同；如果一樣大則選左
>
> $\rightarrow$ 右下角為 LCS 值

例子：
> 算 ``m[2,5]`` 的時候，local optimal 為 2625+1000，由 2625 對上去看 index ``j`` 知切在 $A_3$ 後面

## Longest Palindrome subsequence

從某個 String $S$ 中找出最長的 palindrome，可以刪除（不取）char，例如：
> "ADMA" 最長的 Palindrome subsequence 是刪掉 D 或 M 得到 "AMA" 或 "ADA"

Given string $S$ of length n

$L(i,j) := \ Longest \ Palindrome \ subsequence \ in \ S[i..j]$
> $L(i,j)$ is defined for $1 \le i \le n$, $1 \le j \le n$, $j \ge i-1$
>> - i 和 j 當然要從這 n 個 char 中取，所以我們取的 index 介於 i, j 之間
>> - 右邊的 index j 最小可以比 i 小 1，代表左邊的 index 比右邊還大，這樣還能有定義有點違反直覺（subsequence 根本不存在，最短應該要是 i=j，長度為 1），但是是為了下方 equation 的設計，將這個情況的值定成 0

:::info
$L(i,j) =
\begin{cases}
0 & \mbox{if }\mbox{i = j+1}\\
1 & \mbox{if }\mbox{i = j}\\
L(i+1,j-1)+2& \mbox{if }\mbox{i < j and s[i] = s[j]}\\
max\{L(i+1,j),\ L(i,j-1)\}& \mbox{if }\mbox{i < j and s[i] != s[j]}
\end{cases}$
:::
> 四種 cases 由上到下依序為：
> 1. subsequence 不存在所以長度 = 0
> 2. subsequence 只有一個 char，所以算是一個長度為 1 的 palindrome
> 3. 遞迴看扣除最左最右的 char，中間的 longest palindrome subsequence 有多長，因為此條件假設最左最右相同，所以再把兩個 char 長加上去
> 4. 如果最左最右的 char 不相同，遞迴看扣掉最左的 char 產生的 longest palindrome subsequence 較長還是扣掉右邊的較長

例子：
> 105 台
>

## Huffman Code

稍微詳細一點的 [Huffman Code筆記](https://hackmd.io/@pipibear/HJKvLjUD6)
> 以下幾點的解釋、例子可參考此筆記

- 只有 ==full== binary tree 才能 correspond to an optimal prefix code
> 如果用兩個 bit 來編碼的話
> full binary tree: 所有 node 的 degree 不是 0 就是 2
- 一棵 Ternary Huffman tree 中最多只會出現一個 internal node 具 2 children
- Huffman Code 不一定唯一
- Huffman Tree 非 BST，node 大小不需按照順序
- 如果是 Huffman Code，會滿足下方公式：

$\begin{multline*}∑_{∀i\ : \ external \ node} 2 ^ {−𝑙𝑖} = 1 \\ where \ 𝑙𝑖: external \ node \ i \ 的 \ length\end{multline*}$

## KMP

- prefix function: index 從 1 開始
$\rightarrow$ init val <font color = "green">$\pi[1]=0$</font>
> $P$ 的 prefix 中，比 $P_1$ 短，且是 $P_1$ 的 suffix 的 subsequence 最長有多長
> 因為 $P_1$ 為 Pattern 的前一位，所以比 $P_1$ 短即長度等於零，所以 $\pi[1]=0$
- failure function: index 從 0 開始
$\rightarrow$ init val <font color = "green">$f(0)=-1$</font>



---
# Graph

- a ==cycle== in a graph must be a <font color = "red">simple path</font>

## Edge 分類



## BFS / DFS

BFS 和 DFS 如果用 adjacency list， time 都是 $O(V + E)$
$\rightarrow$ 皆為 linear time

> adjacency list 例子

### BFS


- 用 adjacency list: <font color = "red">$O(V + E)$</font>
- 用 adjacency matrix: <font color = "red">$O(V^2)$</font>
- BFS 用 queue
- BFS 無向圖只會 search 完 connected component，如果 graph 非 connected，會有部分沒 search 到
- 解 tree diameter 的問題：用兩次 BFS
> diameter: 在整棵 tree 裡面任兩點間最短距離的最大值
>
> 假設 a, b 之間的最短距離是某個 tree 的 diameter （在整棵 tree 中，距離最遠的兩點是 a, b）
> 對 tree 中任何一點做一次 BFS 可以找到 a 或 b（或兩者）做為離 s 最遠的點，再對找到的 a / b 做一次 BFS 就可以找到 diameter
- BFS 無向圖產生的 BFS tree 中， non-tree edge 兩端的 vertex level 最多只差 1

### DFS


- ==DFS 無向圖== 只有 <font color = "red">tree edge / back edge</font>
- DFS 用 stack
- 可偵測是否有 cycle
> 有 back edge = 有 cycle


## Topological sort


- 另一種 Topological sort 的方法：
:::success
不斷找出 in-degree 是 0 的 vertex，output 此點，再移除所有從這個點連出去的邊，再找下個 in-degree 是 0 的 vertex repeat
:::

$\rightarrow$ time 也是 $O(V+E)$
> 建立一個每個點的 indegree list，不斷 extract indegree 是零的點
> 一定有這樣的點存在，否則有 cycle
>> 出自 CLRS 22.4-5
- $\exists$ Topological sort $\leftrightarrow$ acyclic
- 如果 Graph 中有 ==Hamiltonian path==，topological sort ++unique++；反之如果沒有 Hamiltonian path，可能有多組 valid 的 topological sort

## Union and Find

用 <font color = "green">linked list</font> 的 time
- ``make-set(x)`` <font color = "red"> $O(1)$</font>
> 建一個只有一個 node 的 linked list
- ``find-set(x)`` <font color = "red"> $O(1)$</font>
> 假設每個 node 都有一個 pointer 指到 set，且 set 也有一個 pointer 指向 head 的情況下
>> 可參考下方圖
- ``union(x,y)`` <font color = "red"> $O(n)$</font>
> 把 y 所在的 list append 到 x 所在的 list，因為有 tail pointer，所以可以快速找到 x 的最後一個 node（要 append 的地方），但是所有 y 的 list 中的 element 都要改為指向 x 的 set，所以要改 「y 的 element 數」個 pointer
>
> 因此， worst case 是我們把一個很長的 list ｙ append 到很短的 list x
> 假設我們共有 n 個 element，最糟的情況是這 n 個分成兩個 list，一個只有一個 element，另個有 n-1 個 element，我們把 n-1 個 element 的 list append 到一個 element 的 list，共修改了 $O(n)$ 個 pointer
>> 可參考下方圖
>>
>> 另外，也因為把很長的 list append 到很短的 list 這件事有點沒效率，所以我們就想，乾脆為每個 list 多 maintain 一個 list 長好了，這樣每次就能把短的 append 到長的，這樣就不用修改那麼多 pointer，這就是 weighted-union heuristic
>> 如果是這樣的情況（++linked list + weighted-union heuristic++）
>> ``union(x,y)`` time = <font color = "red"> $O(logn)$</font>

如果 disjoint sets 用 linked list 串連，假設有兩個 Set $S_1$ 和 $S_2$
假設我們要做 ``union(S1,S2)`` 把 $S_2$ 整個 list 接到 $S_1$ 後面，就需要改所有 $S_2$ 中 elements 的 pointer


<font color = "snake">weighted-union heuristic</font>
> 假設我們有 maintain 每個 list 的長度，我們就可以都選擇把比較短的 list append 到比較長的 list，如果兩個 list 長度相同就任意選擇，這樣的做法就叫做 weighted-union heuristic

<font color = "snake">union by rank</font>
> 在 ``union()`` 的時候，讓 node 比較少的 tree 指向 node 比較多的 tree，不過不是直接去 track 每個 subtree 的 node 數，而是對每個 node 去 maintain 一個值叫做<font color = "snake"> rank</font>，代表++這個 node height 的 upper bound++

<font color = "snake">path compression</font>
> 在做 ``find-set(x)`` 時，把 find path 上的每個 node 都改為指向 root
>
> 109 交 7. 的寫法：
> make each node of a tree in the disjoint-set forest point to the tree root during ++a certain operation++（指的就是``find-set()``）

- <font color = "red">path compression 不會改變 rank</font>
- ``find-set()`` 的時間 depends on path length
- <font color = "red">最多 $|E|$ 次 ``find-set()``</font>


> Tarjan: m weighted union and find with path compression of n elements
> $\rightarrow$ Worst: $O(m \ log^*n)$
> $\rightarrow$ 即 amortized constant time

## 找 equivalence class

$\rightarrow$ <font color = "green">BFS</font>
$\rightarrow$ <font color = "green">union & find</font>

> 因為 equivalence class 等同於 graph 裡的 connected component (關係：is reachable from)
>> 例如假設某個 graph 是 {a, b, c} 三個點的三角形，三個點間彼此都相連，所以整個 graph 是一個 connected component
>> 任兩點間都存在 reachable from 的關係所以 aRb, bRa, bRc, cRb, cRa, aRc
>> $\rightarrow$ [a] = {a, b, c}



## 找 SCC

<font color = "snake">SCC: strongly connected component</font>
> ++maximal++ strongly connected subgraph

<font color = "snake">strongly connected</font>
> Given $G=(V,E)$
> $\forall u, v \in V$
> $\quad \exists$ path from $u$ to $v$
> $\quad \exists$ path from $v$ to $u$


方法：
$\rightarrow$ 對每個 unvisited 的點做 <font color = "green">DFS</font> 或 <font color = "green">BFS</font>

scc 等同於 equivalence class (關係：are mutually reachable)

## MST

[MST筆記](https://hackmd.io/nlISKoNrRwSbuJFHIZBNiQ?view)

- Kruskal: $O(ElogV)$
- Prim: $O(E + VlogV)$ **用Fib Heap，邊比點多很多時 time 較好*

> 112 交 4.、臺師 109
- Kruskal ／ Prim 有負邊也可用（Dijkstra 才不能有負邊）
- 用 Prim 的話，start vertex 不管選哪個，都不會改變 MST 的++值++

### 易混淆是非題
>1. MST 中的 edge 必為某個 cut 的 Light edge
>>因為還沒建構出 spanning tree 前，我們可以不斷加入 safe edge來形成 MST，而要是 Light edge 才能當 safe edge
>2. 各個 cut 的 Light edge 所成的集合不一定會形成 MST
>3. Min weight edge 必在**某個** MST 中
>4. 若每個 Cut 都有 unique light edge，則此 Graph MST unique
>>反之錯：若某 Graph 的 MST unique，不一定每個 Cut 都有 unique 的 light edge
>5. （用某個 Weight function) decrease MST 中其中一個 edge 的 weight，結果仍為 MST
>6. 去掉在 cycle 上的 max weight edge 後，剩餘的邊仍可形成原圖的 MST

## Shortest Path


> 109 台

- ==BFS== 的 $O(V+E)$ 如果是++任意的 graph++，則須為 <font color = "red">unweighted</font>，邊則是有向或無向都可以；如果是對 ++tree++（undirected），因為到任何點都只有一條 unique path，所以就算 weighted 也可達到 $O(V+E)$，同理 DFS 也是
- ==DAG== 找 shortest path 可達 <font color = "red">linear time</font>
- ==Bellman-Ford== 可++偵測 negative cycle++


- 只要是 Dijkstra, Bellman-Ford ==Space== 都是 <font color = "red">$O(V)$</font>
- <font color = "red">Dijkstra 可以有 cycle</font> （只要++不是負 cycle++）
- 雖然對所有問題來說， Greedy 不一定會得到 optimal result，但 Dijkstra 是 Greedy，且有 optimal result
> 101 交
- 「<font color = "prince">給一個無向圖和一個正整數 k，如果所有邊的長度都是 1 ，且每個點恰好走一次，問是否有 path 長度++最多++是 k</font>」等同問 shortest path

### relax

> Dijkstra 和 DAG 對每個邊 relax 一次
> Bellman-Ford 對每個邊 relax $|V|-1$ 次

### DAG

DAG 用 topological sort，如果忘記 topological sort 是什麼，下方是 topological sort 的 code，接著才是 DAG 的 code


> DAG 的 time 裡的 dominating term 就是 topological sort，所以時間相同

### Dijkstra

| | init | extract-min | decrease-key | total |
| -------------- | ---------------------- | ----------------------------------------- | ---------------------------- | --- |
| | 存所有邊的 weight | greedy 挑 weight 最小的 edge V 次 | relax 共 $E$ 次 | |
| array | $O(V)$ | $V\times O(V)$ 全部掃過 | $E\times O(1)$ 直接改 | $O(V^2)$ |
| Bin (Min) Heap | $O(V)$ bottom-up | $V\times O(logV)$ 要 Heapify | $E\times O(logV)$ 要 Heapify | $O((V+E)logV)$ |
| Fib Heap | $O(V)$ ``insert()``x V | $V\times O(logV)$ 從 root list 找下個 min | $E\times O(1)$ | $O(VlogV+E)$ |

> Fib Heap: <font color = "green">Insert, Union, decrease-key</font> $\rightarrow$ amortized $O(1)$



- 如果 while loop （挑 weight 最小 = 從 min queue dequeue）<font color = "red">只 run $V-1$ 輪，Dijkstra 結果仍然正確</font>

### Bellman-Ford


> 104 交


> 109 台

if ==Bellman Ford 有 negative cycle==
- <font color = "red">++必有++某個點的最短距離 output 是錯的</font>
- 求 ++longest path++，就算沒有 $\ge0$ 的 cycle，也是錯的
> 可參考下一節 longest path
- 會求出 source 到某個給定的 destination 的 ++shortest acyclic path++

### Floyd-Warshall

- 可以拿來偵測 negative cycle
> 如果最後一輪（第 $|V|$ 輪）有某個 vertex 自己到自己的距離 $< 0$，則有 negative cycle


用兩個 array：
1. $W^k$：紀錄值
> 代表只允許經過點 1~k 的 all pairs shortest path
2. $\Pi^k$：紀錄 parent
> 代表只允許經過點 1~k 的情況下，shortest path 是從哪個點走來

<font color = "green">init value</font>
1. $W^0$
- 自己走到自己 $\rightarrow$ 0
- 走不到 $\rightarrow$ $\infty$
- u 可走到 v $\rightarrow$ edge (u,v) 的值
2. $\Pi^0$
- 自己走到自己／走不到 $\rightarrow$ $Nil$
- u 可走到 v $\rightarrow$ u

方法：
- 算 $W^1$ 時查 $W^0$，框第一列第一行，對應項相加看是否比較小
> 算 $W^2$ 時查 $W^1$，框第二列第二行⋯⋯其餘同理
- 算 $W^1$ 時如果有更新值，看 $\Pi^0$ 的第一列更新 $\Pi^1$
> 算 $W^2$ 時如果有更新值，看 $\Pi^1$ 的第二列更新 $\Pi^2$⋯⋯其餘同理

$\rightarrow$ 共做 $|V|$ 輪（做到 $W^{V}$、$\Pi^{V}$）

> 102 交
- 如果只允許經某點 u，寫完 $W^0$、$\Pi^0$ 後，框 u 對應的那列那行，做與上述同樣的事，做一輪即結束

> 104 交


### Johnson

==all pairs== shortest path
Johnson time = <font color = "red">$O(V^2lgV + VE)$</font>
> if 用 ==fibonacci heap==

概念：
> 把 Dijkstra 和 Bellman-Ford 當作 subroutine，先用 Bellman-Ford 偵測有沒有負環，有的話 output 錯誤；如果沒有負環，再 reweight 讓所有邊都變成正的，接著再用 Dijkstra 對每個點做對所有其他點的 single source shortest path

- reweight 成所有邊都正的方法：


- <font color = "red">reweight 不會改變 shortest path</font>
> 但並非隨意 reweight
> 例如：
> - 把某個圖的所有邊 weight 都加一，原 shortest path reweight 後不一定會還是 shortest path
>> 103 交、 109 台
> - 把所有 edge weight 都變成原來的兩倍，shortest path 不改變
>> 乘++正數++不影響

> reweight 例子


> reweight 成任何實數都成立，不一定要是正的，所以++就算 $G'$ 中沒有負環++，也<font color = "red">不能把 Bellman-Ford 換成 Dijkstra</font>

- 如果是 ++sparse++ graph 比 Floyd Warshall 快

### 應用

#### 求 critical path
- time: <font color = "red">$\theta(V+E)$</font>

<font color = "snake">Critical Path</font>: longest path through DAG

求 critical path 的方法：

【法一】

1. 把所有 edge 的<font color = "green">正負對調</font>
2. run DAG_Shortest_Path 的 Algo

【法二】

直接 run DAG_Shortest_Path 的 Algo
> 做 topological sort，依序對 topological sort result 中的點 relax
但是
- relax initialize 的時候 $\infty$ 改 $-\infty$
- relax 過程中比大小的 $>$ 改 $<$
> 取長的 path

例子：
> 104 交


#### system of difference constraints

用 shortest path 解，首先畫 constraint graph：

> 所有出現的變數都設成一個 vertex，以下圖的式子為例，vertices 由 $x_1 \sim x_5$ 設成 $v_1 \sim v_5$
> 除此之外再多設一個點 $v_0$，連到所有其他的點（$v_1 \sim v_5$），且這些邊的 weight 都設成 0
> 其餘各個點間的邊則是如果算式是 $a-b \le c$ 就畫一條 $b$ 到 $a$ 的邊且 weight $= c$


轉換成 constraint graph 即下圖：


$x_1 \sim x_5$ 的解即 $v_0$ 到 $v_1 \sim v_5$ 各自的最短距離
> 舉上圖中例子來說，$v_0$ 到 $v_1$ 的 shortest path 是從：
> $v_0 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5 \rightarrow v_1$
> 共 $0+(-1)+(-3)+(-1)=(-5)$
> 所以 $v_1$ 對應的 $x_1$ 以及其他 shortest path length 形成一組解

> 上圖例子的解

> - 如果有負環則此系統無解


---
## Longest Path

> 本節截圖來源：
> - [NTU EE ppt](http://cc.ee.ntu.edu.tw/~ywchang/Courses/EDA/lec4.pdf)
> - [MIT lecture notes](https://courses.csail.mit.edu/6.006/fall11/lectures/lecture17.pdf)

> 差別只在於黃色螢光筆處
> $\rightarrow$ 如果有比較長的 path 就換成比較長的
> - 能在 $O(V+E)$ 中找到 longest path，但是 graph 須為 directed acyclic
>> - <font color = "red">如果是 DAG ，無論 longest / shortest path 都可在 ++linear++ time 中找到解</font>


> 如果找 longest path 時有負環不影響，因為要挑的是長的，負環只會讓 path 越來越短，所以不會挑到


> 如果直接把某個 Graph 的所有邊的 weight 都乘 $-1$ 不一定能得到 longest path，因為如果本來有 negative cycle，乘 $-1$ 後變成有 positive cycle


---
## flow network

稍微詳細一點的 [flow network 筆記](https://hackmd.io/@pipibear/Skuv9lZYT)

### Ford Fulkerson


- 雖然 max-flow problem 大部分的 capacity 都是整數，但是<font color = "red">++有理數++也可以</font>！
> 因為可透過轉換把所有邊的 capacity 都調成整數

- Ford Fulkerson 的 time = <font color = "red">$O(|E|f^*)$</font>
> $f^*$: scaling transformation 後，++transformed network 裡的 max flow++

### Edmonds Karp

找 augmenting path 用 BFS，其餘與 Ford Fulkerson 相同

- Edmonds Karp time = <font color = "red">$O(VE^2)$／$O(V^2E)$</font>
> 前者為 CLRS 解答，後者為交大解答
- <font color = "red">最多增加 $O(VE)$ 條 augmenting path</font>

### Push relabel

- Push relabel time = $O(V^3)$
> 可達 polynomial time

### 考古補充
#### maximum flow by scaling

CLRS 26-5


> 108 交 12. (24-26 小題)

Q. 如何在 $O(E)$ 內找到一條 capacity 至少是 $K$ 的 augmenting path （b 小題）
> 在 residual network 要挑 path 時，只要有某個 edge 的 capacity 比 k 小，就無法 augment 那條 path
因此，我們只需要把 residual network 上所有 capacity 比 k 小的 edge 移除，我們就可以再 run BFS 找 augmenting path

Q. Why time = <font color = "red">$O(E^2lgC)$</font> （f 小題）
> $K$ 在 while loop 裡每次會除 2
> 所以共做 $lg(2^{\lfloor lgC\rfloor})$ 次
> 也就等同 $\lfloor lgC\rfloor = O(lgC)$ 次
>
> 根據前一小題（e 小題），每一輪增加 augmenting path 的次數至多 $O(E)$ 次
>
> 再根據 b 小題（也就是前一個 Q.）每次增加一條 augmenting path 要花的時間為 $O(E)$
>
> $\rightarrow$ 所以 while loop 的每一輪花的時間 $= O(E^2)$ 乘上 loop $O(lgC)$ 次，即為所求的 $O(E^2lgC)$

- 就算所有的 edge capacity 都不相同，也不一定會有 unique min cut
- 當找不到 augmenting path 時，將起點 s 和「與 s 相連的所有 vertices」加入 set $S$，則 $S$ 和 $V-S$ 形成一個 minimum cut
- 假設對應 max flow 的 min cut 是 $(S,T)$，則所有 $S$ 到 $T$ 的 residual capacity 都為 0
> 即 min cut $S$ 到 $T$ 的所有邊都流滿
- <font color = "red">即使所有邊的 capacity 都是整數，max flow 可能在某些邊上有不為整數的 flow</font>

---
# Sorting

## Heapsort

### Heapify Worst Case

> 調整 Heap 高度（heapify）的 Worst case time complexity = $O(logn)$
> 發生在最後一層只有剛好一半，root 左子樹佔全部的 $2\over3$ 的時候

大概是長這樣：


證明：

## Quicksort


- Quick sort sorts in place
- Quick sort <font color = "red">not stable</font>
- worst case 發生在++所有 element 值都相同時++，或是 ++array 值從大排到小++，時間退化到同 insertion sort 為 $\theta(n^2)$
> 因為值從大排到小 pivot 會挑到最小的 element 造成 $\le x$ 的部分個數為零

- 不管是一般的 quicksort 或是 randomized-quicksort，worst case 皆為 $\theta(n^2)$
- <font color = "green">median of 3</font> method 只會影響 constant factor，所以 time complexity 無法更低
> 在 best case 下仍為 $\Omega(nlogn)$

## Counting sort 最後要產生 output array：

**A:** 原本 input 的 array
**B:** 要 output 的 array
**C:** 紀錄 input 的 array A 裡面的 element 出現幾次的 Array

>每次把一個 element 放到 output 的 array B 中之後，此 element 的數量少一（i.e. array C 對應的值減少）
>>放的順序：
>>假設 output 時有 element 要放到 output array B 的第 1-3 格，是先放到第三格，接著才是第二格，最後才是第一格

---
# Tree

## Spanning Tree

### 個數計算
### 產生 (min) spanning tree 的方法
答案 A, B, E

(B) 不確定B, C 的理由，猜測與 matroid 相關，但我不熟 XD
*參考 CLRS p.439*

假設 M(G) 是一個 connected, undirected graph G 的 matroid
By Thm16.6（所有 matroid 中的 maximal independent subset 大小都相同）
→ M(G) 必為連結 G 中所有點的 free tree (因為是 tree 所以邊數必為點數-1 = maximal independent subset，比點數-1 大就非 independent)
∴ M(G) 為 G 的一個 spanning tree

>Lemma 16.7: Matroid 有 Greedy choice property
>Lemma 16.10: Matroid 有 Optimal Substructure

因此我們可以透過這種 Greedy 的方式建立 spanning tree。

我原本的想法：
對每個點除了 s 都取和它相鄰的一邊，代表會取到 $|V|-1$ 邊，因此必為會連到所有點的 spanning tree。
好像對但也不太確定，待確認後再補。

> [matroid 筆記](https://hackmd.io/0RBNINUNS8SVDGdQbi2PEA)

## m-ary tree

> Complete m-ary tree: 除了 leaves 以外，其餘 vertices degree 都是 m

### 比賽數量問題

選手數 $\rightarrow$ leaves 數
一場比賽幾個人 $\rightarrow$ m
總共需要比幾場 $\rightarrow$ i
> i: #internal node


### 找偽幣

硬幣數量取 log，以「一次可以比幾個硬幣」為底


## leftist tree

leftist tree 是 mergeable heap
- <font color = "red">merge</font> 兩個 leftist tree, <font color = "red">insert</font> arbitrary,<font color = "red"> delete</font>-min/max 都是 ==$O(logn)$==

> 因為 insert 和 delete 都是 based on merge
> insert $\rightarrow$ 把要 insert 的當作一個 node 的 leftist tree 再 merge
> delete $\rightarrow$ merge 要 delete 的 node 的 left, right subtree

> 實際上 merge time = $O( \ log(n_1+n_2 ) \ )$
>> $n_1, n_2$ 是兩棵 leftist tree 的 node 數

## binomial tree/ heap


## AVL Tree

### 所需 node 數

AVL tree ，最少 node 情況的樣子（此圖 $T_i$ 的 height i 是假設 root = 0，上圖公式是假設 root = 1！）

## Red Black Tree

- <font color = "red">紅黑樹可以所有 node 都是黑的！</font>

> 112 交 10.
- 超過三個 node 以上的紅黑樹，<font color = "red">黑色至少有 $M \over 2$</font>
>$M: \#internal\ node + \#external \ node$
- 如果<font color = "red">只看 internal nodes，紅最多的情況下，紅：黑 $=2:1$</font>
> 每個 黑點都有兩個 red child node
- 除非把 root 刪掉，不然不可能刪掉所有的黑色節點

==$bh(x)$== black height of x
> 從某個 node x （不包含他自己）到 leaf 的 simple path 上的 black node 數


- 從 root 到任何一個 ``NIL`` (external node) 所經過的 path 至少一半是黑的，即 $bh(x) \ge \frac {h}{2}$
> 因為每多一個紅色節點一定會跟著多一個黑的（因為不能有連續紅）

:::success
具 n internal nodes 的 red black tree:

$lg(n+1) \le height \le 2lg(n+1)$

> $height = O(logn)$

:::

### 特性：Red Black Tree isom. 2-3-4 tree

> 參考資料：[Stanford lecture notes](https://web.stanford.edu/class/archive/cs/cs166/cs166.1206/lectures/06/Small06.pdf)


> 3 node 往右則大的 key 為紅色，往左則是小的 key 為紅色
> i.e. 上面的必為黑色

> 111 台大 14.
> Consider a red-black tree with n internal nodes, where n is even. At most how many of them can be a black node with one red child?

猜測答案為 $n\over2$
$\rightarrow$ 轉換成 2-3-4 tree 去想，所有 node 皆為 3 node (2 keys)，每兩個 keys 會形成一個 black node with 1 red node，因此 n 個 internal nodes 共可形成 $n\over2$ 組

## B Tree

更多例子的 B Tree 筆記（補連結）

- DS 給 ==order== 假設為 r
> root: $\ \qquad\qquad2 \le deg(root)\le r$
> root 以外：$\qquad\lceil{\frac{r}{2}}\rceil \le deg(x)\le r$
- Algo 給 ==min degree== 假設為 t
> root: $\qquad\qquad2 \le deg(root)\le 2t$
> root 以外：$\qquad t \le deg(x)\le 2t$

### insert

基本題型： 給一串數字求 insert 完的 B tree

1. 如果一開始從空樹開始 insert，則先全 insert 到 root，直到 root 的 key 滿
2. root 滿之後才開始從中間 split

（直接看例子）
> B tree of order 3 代表：
> $2 \le deg(root)\le 3$
>> root 的 degree 一律固定 $\ge 2$
>>
> root 以外的任何 node $x$ 滿足
> $\lceil{\frac{order}{2}}\rceil \le deg(x)\le 3$
> 因此也和 root 相同，$2 \le deg(x)\le 3$
>
> $\rightarrow$ B tree of order 3 又稱 2-3 tree，所有 node 的 degree 都為二或三

- insert 到 B Tree 時皆是 <font color = "green">insert 到 leaf</font>
- insert 時如果 node full （key 數 = 2t-1）就要 split，把 median 左右分成兩個 nodes，各 t-1 個 keys， median 放到原本 full 的這個 node 的 parent node
- 如果 split 時， parent node 也 full，則 parent node 也要 split
- 有可能一路往上 split
- root node 沒滿時不會被 split
- ==root 被 split $\leftrightarrow$ 樹高增加==
- <font color = "red">所有 leaves 都在同一層</font>

> 或 $log_t(2t^h) \le log_t(n+1))$


證明：
> 因為 root 的 min degree = 2，所以 root 至少有 1 個 key，其餘所有 node degree 都 $\ge t$，所以都至少有 t-1 個 key，從第二層（depth = 1）開始每層 node 數都是 $2t^{i-1}$，會有一個 2 是因為根據定義，只有 root 可以不用 $\ge$ minimum degree， root degree 只要 $\ge 2$ 就好，所以 root 下來的那層只有兩個 node

---
# 其餘 Topics

## 分類

> 103 交
- Heapsort 並非 Greedy，也非 DP，也不是 Divide and conquer
- ==Finding maximum independent set in interval graph== 是 <font color = "red">Greedy</font>
> 此問題等價於 ==avtivity selection problem==
> $\rightarrow$ 每次選 <font color = "red">++finish time++ 最早</font>的 activity 執行，就能完成最多的 activities

## Hashing

更詳細的 hashing 筆記（補連結）

1. 如果是 simple uniform hashing，且用 chaining

> 兩個 element hash 到同位置的機率是 $1\over m$
>> m 是 hash table 大小

- 不管前面已經放了多少個 element 進 hash table 再多放兩個進來， hash 到同位置的機率仍是 $1\over m$

2. 如果是 open addressing，已經 hash 了 n 個 element 到 hash table（n 比 hash table 的大小 m 要來得小，也就是 hash table 還沒滿），假設是 uniform hashing ，再多 insert 一個 element 的 expected cost = $1 \over 1- {n \over m}$


3. 假設是 uniform hashing、open addressing，且已經 insert 兩個 key 了，則第三個 key 恰好需要 probe 三次才能 insert 進去的機率：


## Shortest pair
- divide and conquer
- time: <font color = "red">$\theta(nlogn)$</font>

> Cormen 沒圖，用離散 Rosen 的圖，所有的 $d$ 即下文中用的 $\delta$

1. 用兩次 merge sort
- 第一次根據 x 軸值由小到大排
> 放在 array $X$
- 第二次根據 y 軸值由小到大排
> 放在 array $Y$

time = $2 \times O(nlogn) = O(nlogn)$
> $\rightarrow$ 從頭到尾只要排這兩次就好，我們不能在每個 recursive step 都排，否則時間會超過 $O(nlogn)$ （我們希望求的 closest pair time）
2. recursive step：
根據 sort 好的 list，取 x 軸正中間的值畫一條垂直線 $l$，將所有的點分成兩邊，兩邊各含 $n \over 2$ 個點
$\rightarrow$ 每次分出兩個 subproblems，大小為 $n \over 2$
3. 分成兩邊以後，做兩個 recurive call
- [x] 對所有在左邊的點找出 closest pair，令左邊 closest pair 回傳的值為 $\delta_L$
- [x] 對所有在右邊的點找出 closest pair，令右邊 closest pair 回傳的值為 $\delta_R$
$\rightarrow$ 令 $\delta = min\{\delta_L,\delta_R\}$
- 遞迴切到 $\le 3$ 個點時就直接暴力法檢查這幾個點彼此間的距離
> 因為 closest pair 的兩個點只有三種可能：
>
> $Case 1:$ 兩個點都在 $l$ 的左側
> $Case 2:$ 兩個點都在 $l$ 的右側
> $Case 3:$ 一個點在 $l$ 的左側，一個點在 $l$ 的右側
>
> 所以在求得 $\delta$ 以後，我們已經處理完前兩種可能， closest pair 的值要嘛是 $\delta$，要嘛是我們接下來要算的 $Case 3$

觀察：
> 如果有某兩點在 $l$ 的左右為 closest pair，代表此兩點一定在 $l$ 左右各 $\delta$ 的範圍內
>> $\because$ 最極端的情況，剛好有一點在 $l$ 上，另一點剛好距離 $l$ $\delta$，便會造成兩點距離 $= \delta$
>> 如果有任何一點超過 $l$ $\delta$，就不可能兩點各在 $l$ 的兩側，距離又 $\le \delta$


有了這個觀念後再來找：
是否存在某兩點在 $l$ 的左右為 closest pair（$Case 3$）

4. 首先先把不在 $l$ 的左右各 $\delta$ 範圍內的點去除
5. 剩下的（圖中的 $v_1\sim v_8$）因為前面已經 merge sort 過了，所以我們就再建一個 sorted 的 array $Y'$ 取 $Y$ 中符合條件的這些點（$Y'$ 照順序取即可，不用再 sort）
6. 接著從 $Y'$ 裡挑點照順序檢查，此圖中即先檢查 $v_1$ <font color = "red">和他後面++七個點++之間的距離是否 $< \delta$</font>

Q. ++為什麼是檢查 7 個點？++

$\because$ 鴿籠原理

> 首先，如果要長度 $\le \delta$ ，兩個點必定要落在這個灰色長方形中，那這個長方形中最多有可能出現多少個點呢？
> 先考慮左邊的正方形：
> 這個正方形中最多只有可能有 4 個點
>> 假設有第五個點 $u$，根據鴿籠原理，打叉的這四塊三角形裡要放五個點，必定有兩點在同一塊三角形中，也就是這兩個點的距離 $< \delta$
>> $\rightarrow$ 但是，因為這兩點同樣都在左側，所以就矛盾我們前面說 $\delta$ 是兩個點在同側的情況下的最小距離
>
> 因此，如果落在 $l$ 上的點我們算在左側也算在右側，總共最多會有 8 個點，假設我們是因為在 $Y'$ 中挑到 $v_1$ 才來檢查這個長方形，扣掉 $v_1$ 我們要再檢查 7 個點（$v_2$, $v_5$ 各算兩次的情況下）

因為刪掉 $l$ 左右 $\delta$ 之外的點後，剩下的點數 $=O(n)$
> 假設原來 n 個點，刪完必定 $\le n$

每個點都往後檢查 7 個點 $=7 \times O(n) = O(n)$
因此，找 $Case 3$ 花費時間 $O(n)$

最後終於得到遞迴關係式
:::success
$T(n)=2T({n \over 2}) + \theta(n)$
:::

利用 Master Thm，可得 time = $\theta(nlogn)$
再加上 merge sort time $\theta(nlogn)$
仍為 $\theta(nlogn)$