# 大二下 - Algorithms - Note
###### tags: `大二下` `演算法`
Lecture 7 - Counting Sort
---
* **Complexity of Sorting** (For problem X)
1. **Upper bound**: 某algo需要的**最大成本** Big-O(O)
2. **Lower bound**: 對所有解決X的algo的成本 Omega
3. **Optimal algo**: Upper bound = Lower bound 時為最佳algorithm

* Decision tree
* height比較最多次
* leaf node : n! (n = node數)
* 任何compare-based(以比較為基礎的)sorting algorithm的worst case必須最少**lg(N!)~NlgN次**的比較
>:::info
>:bulb: pf:
>高度h Full-binary tree有 2^h leaf node
>N個elements -> N! 個排列可能
>2^h >= N! ->
>h >= lgN! ->
>h >= NlgN
>:::

* **key-indexed counting sort**

* 教授給的idea
1. 先算個別出現幾次

|a|b|c|d|e|
| -------- | -------- | -------- |--------|--------|
|2|1|2|1|2|

2. 累加

|a|b|c|d|e|
| -------- | -------- | -------- |--------|--------|
|2|1|2|1|2|
|2|3|5|6|8|

3. Shift

|a|b|c|d|e| |
| -------- | -------- | -------- | -------- | -------- | -------- |
|2|1|2|1|2||
|0|2|3|5|6|8|

4. 填表(按照題目順序看 查shift的index去填表 然後shift update+1)

* 分析:
R = size
- Time complexity: O(n+R) -> O(n)
<非比較基礎algo>
- 需要額外N+R的space
- Stable
* **LSD radix sort**
* 從最小位元開始比大小
* Stable
* N = 4 (data)
* R = 9 (1-9)
* 36**9** 9**1**1 **9**11 367
* 36**7** 4**2**5 **4**25 369
* 42**5** 3**6**7 **3**67 425
* 91**1** 3**6**9 **3**69 911
* W (N + R)

* **MSD radix sort**
* 依次只根據1-bit比大小(最高位元開始)
* Stable
* N = 4 (data)
* R = 9 (1-9)
* 找上一個位元一樣的人去一起排序 不然會亂掉
* 問題點:subarray切太小時 N << R 效率低 -> 要花很久accumulate table
* 


Lecture 8 - Heap Sort
---
>binary tree
>complete tree
>parents' value >= children's value
* **可以用array表示heap**
>找parent: index/2(下高斯)
:::warning
:question: 考點1：為何不從index 0開始填入？
:ballot_box_with_check: 因為才能用下高斯找parent
:::
* **Top-M problem**

* ***Option 1***
* insert() = **O(M)**
* del() = **O(M)**
* 
* ***Option 2***
* insert() = **O(M)**
* del() = **O(1)**
* 

* 只有少少memory 要把後來加入的放進去 必須剔除最小的傢伙

* **Binary heap**
* Height of **complete tree** with N nodes = 下高斯 ⎣lg N⎦
* parent node > 所有 children node
* 插入一個新node在尾端
* swim up
* 成本: ~**lg N** compares
* 
* 避免小孩 > 父親
* 
* 拔掉Max
* 
* 把H往下sink
* 成本: **2 lg N** compares (child + parent 比兩輪)
* 
* 
:::warning
:question: 考點2：Heap是否一定要binary,是否可以用trinary?
:ballot_box_with_check: 雖然在swim-up時會快，但是sink-down時比較麻煩要跟3個做比較
:::

* **Priority queue (PQ)**
>賦予queue內資料權重 可以得知誰最重要->要先處理

* 移除max & min 值
* 
* 
* 借用學姊筆記圖
* 

* **In-place heapsort**
* 成本: NlogN 需要額外N space -> **Not Stable**
* sink-based:
* First pass: Build heap using **bottom-up** method
* 不看leaf
* 
* Second pass: Remove the maximum
* sink
* 
* START!!!
* 排好的heap
* 
* 忽略leaf
* 
* 最後sink完父代們 開始刪除Max值
* 

* 分析:
* 
* **≤ 2 N** compares
* **≤ N** exchanges
>
>```
>h(h-0) + 2(h-1) + 4(h-2) + 8(h-3) +...+2^h(h-h)
>= 2^(h+1) - h - 2
>N - (h+1)
><= N
>```
* swim-up: **2 NlgN** (swim-up + del-Max)
* sink-based: **N + N lgN**
* In-place heap的缺點:
* Inner loop longer than quicksort’s
* Makes poor use of cache
* Not stable

* 各種sort

Lecture 9 - Graphs Research
---
* **Graph Representation**
* 複習資結圖論
>到ppt17頁
>1. List of Edge (x1,y1),(x2,y2)...
>2. Adjacency-Matrix n個點需要n^2的space -> 成本高
>
>3. Adjacency-List 通常稀疏(sparse) 不適合真實情況
>

* degree是V頂點連出去的node數

:::info
hw:LSD
:bulb:想法：DFS找最長的最短路徑
:::
* **Path Finding Problem**
>可以創一個arrar紀錄 紀錄剛剛從哪個點來的
* **DFS** (Depth-first Search)
* recursive visit 相鄰邊
* 可以尋找connected components
* >marked[] 標記走過
>edgeTo[] 記路徑 EX: v->w , edgeTo[w]=v
> 
* >recursion
> 

* **BFS** (Breadth-first Search)
* 廣度優先搜索
* 第一個node找完所有鄰居才換人
* 成本: **E + V**
* **Connected Components**
* 檢查是否有路s->t
* union-find vs. DFS
> DFS 生成graph的成本 = E
> 1.Union-find: 可以中途插入edge
> 2.DFS不行,要重新traverse
> 
* Directed Graphs
>DAG = Directed acyclic graph
* 沒cycle <==> topological order*
* check acylic(無迴圈)
* if neighbor was visited -> cycle
*
* Topological sort
* 起始點不重要 但選取的點會影響結果
* 
* dfs
> 

Lecture 10 - Minimum Spanning Trees
---
>spanning tree 定義: 所有node都包含在內 + connected + acyclic
>3種方法 這裡寫2種就好
>Shortest-path tree (SPT)
* **Kruskal's**
1. sort 邊的權重
2. 從小的開始加入邊 造成迴圈的忽略

* Challenge
* Would adding edge v–w to tree T create a cycle?
* Efficient solution
* Use the **union-find**
* >如果v & w在同一個set 則會有cycle
* **Prim's**
1. 選一個起始點找最小邊
2. 找tree現有的邊最小且不會造成cycle的加入tree
3. 直到V-1個邊
* Time complexity:
* 

* **O(VE)**: 找min可以不sort 只要linear search就好
* **O(ElogE)**: 用PQ(heap的)
>每次選擇最小權值的邊時，我們可以利用排序好的邊列表，並使用最小堆等數據結構來快速找到最小權值的邊
* Eager Implementation
* 每增加一個邊就check是否有更小的邊

Lecture 11 - Shortest Paths
---
* **Dijkstra's**
* S到所有點的最短路徑
* **O(ElogV)**
* **Dijkstra's Implementation**
* **PQ**
> 
* **SP on Edge-weighted DAGs**
* 依照拓樸順序看V -> relax相連的所有node
* Dijkstra VS DAG
* Dijkstra : **O(ElogV)** 用在有cycle的graph
>E: 每加入一個edge 就updatePQ
>logV: del Min P(Q)
* DAG : **O(V+E)** 用在無cycle的graph
* 
* 最長路徑 - weighted DAG
* 將所有weight都加上負號 用topological sort找最短路徑
>負越多 -> path越長

* **Bellman-Ford’s Algorithm**
* Negative Weights
* 因為Dijkstra不能有負邊
* disTo\[s\] = 0
* 所有連接到s的node V => disTo\[V\] = ∞
* relax 全部的 V
> 
* 
* 依照Any order check min path
* 總共做 V 輪 -> if last round 還有改變 -> negative cycle
* Oueue-based Bellman-Ford
* if disTo\[V\]在pass i沒有改變 -> 不須relax從V出去的node
* 建立maintain queue放disTo\[V\]那些不改變的點
* Typical case: O(E+V)
>E: 每一輪只有一個邊改變
* Worst case: O(EV)

* **Cost summary**

Lecture 12 - NP completeness
---
* **NP-Complete & 演算法難度(自主學習!!!會考!!!)**
>intractable -> **2^n**
* **Class:**
1. 已被證實可以解的
2. 已被證實是難解的
3. 已被證明無法解決的問題
4. 尚未被證明是難解的 不知道有沒有解 (可能是我們不夠聰明)
* **Class 4** EX:
* SSP
* 2^n -> n個數字 有或沒有(1 or 0)
* 
* TSP
* 2^n
* 

* **Nondeterministic Algorithm**
>unbounded parallelism in computation
>不限制CPU數量
* **P vs NP:**
* P:
>Problems can be solved in polynomial-time
* NP:
>若難解的問題(2^n)可被Nondeterministic解決 => NP
>可被DA驗證
* P & NP糾結的點:
> 

* **Halting Problem**
>**Class 3**
* 用反證法證明Q(Z)不存在 -> 判斷是否植入木馬
* 寫一個程式 當Q發現有植入木馬 就不植木馬
* 反之沒發現木馬 就植入木馬

Lecture 13 - Dynamic Programming
---
* **Fibonacci**
* 用F(n) = F(n-1) + F(n-2)會是把它拆成2個子問題
* T(n) = 2T(n-1) + 1
* O(n^2)
* 用DP => 灰色部分不用做
* T(n) = n + 1
* 
* 把剛才算的fib(0) fib(1)...等等記錄起來 之後直接查找
* top-down (recursive) 大問題拆小處理再加起來
* 
* bottom-up (iteration) 小問題丟給大問題處理
* 
* **Rod Cutting Problem**
* 把大問題漸漸拆成小問題 用DP讚讚
* 
* 教授表示他喜歡iteration版本比較簡單
* 

* **Matrix Chain Multiplication**
* **計算1-3的最小成本 => 兩種情況**
* **這裡是3種情況 (p.s老師算錯中間那個應該要是3x7x8)**

* **自主學習 會考!!!**

* **DP解決All-pair Shortest Path**
* **Floyd-Warshall**
* 透過(node+1)個array 逐漸開放過路權限
* 要設初始array : A^(-1)
* A^1 代表可以透過1這個node通往其他node
* if 有更小的過路費 -> 填入新值
* 
* **DP解決Longest Common Subsequence** (LCS)
* 不可以交叉(e不能算)
* Time complexity: **O(mn)**
* 
* EX:
* When相同char: 左上+1 填入
* If不同: (上,左)取大者 填入
* 
* 找回去的路有爬坡的
*