---
# System prepended metadata

title: Algorithms - Note
tags: [大二下, 演算法]

---

# 大二下 - 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
![](https://hackmd.io/_uploads/BJE1_azD3.png)
    * 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**
![](https://hackmd.io/_uploads/SJd4gCGvh.png)

    * 教授給的idea
    ![](https://hackmd.io/_uploads/H1ypiazwh.png)
        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)
            ![](https://hackmd.io/_uploads/H10cApGv2.png)
            ![](https://hackmd.io/_uploads/rJ_nCaMwh.png)
            ![](https://hackmd.io/_uploads/Sy4RC6Mv3.png)
            
            * 分析:
            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)
![](https://hackmd.io/_uploads/BkuAvAzvn.png)
    
* **MSD radix sort**
    * 依次只根據1-bit比大小(最高位元開始)
        * Stable
        * N = 4 (data)
        * R = 9 (1-9)
    * 找上一個位元一樣的人去一起排序 不然會亂掉
    * 問題點:subarray切太小時 N << R 效率低 -> 要花很久accumulate table
    * ![](https://hackmd.io/_uploads/r1s4jRGw3.png)

![](https://hackmd.io/_uploads/rk6sFCfvh.png)
   

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)**
        * ![](https://hackmd.io/_uploads/HkBwphHwn.png)
    * ***Option 2***
        * insert() = **O(M)**
        * del() = **O(1)**
        * ![](https://hackmd.io/_uploads/HJDQChrwn.png)

    * 只有少少memory 要把後來加入的放進去 必須剔除最小的傢伙
![](https://hackmd.io/_uploads/BJhS2CMvh.png)

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

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

    * 移除max & min 值
    * ![](https://hackmd.io/_uploads/HyapmbLP2.png)
    * ![](https://hackmd.io/_uploads/rJL6lJXw2.png)
    * 借用學姊筆記圖
        * ![](https://hackmd.io/_uploads/H1dZbk7w3.png)

* **In-place heapsort**
    * 成本: NlogN 需要額外N space -> **Not Stable**
    * sink-based:
        * First pass:  Build heap using **bottom-up** method
            * 不看leaf
            * ![](https://hackmd.io/_uploads/SJCUz1XD3.png)
        * Second pass: Remove the maximum
            * sink
            * ![](https://hackmd.io/_uploads/SJxp3f1Qwn.png)
    * START!!!
        * 排好的heap
        * ![](https://hackmd.io/_uploads/HJsb7kQv2.png)
        * 忽略leaf
        * ![](https://hackmd.io/_uploads/HkiXmJQvh.png)
        * 最後sink完父代們 開始刪除Max值
        * ![](https://hackmd.io/_uploads/HyvvXk7vh.png)

    * 分析:
        * ![](https://hackmd.io/_uploads/ryJvE17Pn.png)
        * **≤ 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
![](https://hackmd.io/_uploads/r17ovJQDn.png)

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

        
* degree是V頂點連出去的node數
![](https://hackmd.io/_uploads/SJhGv-8Dn.png)

        


:::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
            > ![](https://hackmd.io/_uploads/Bk_IqJmDn.png)
        * >recursion
            > ![](https://hackmd.io/_uploads/BJpSqyXP3.png)

    * **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
            > ![](https://hackmd.io/_uploads/Syban17Dh.png)
    * Directed Graphs
        >DAG = Directed acyclic graph
        * 沒cycle <==> topological order*
        * check acylic(無迴圈)
            * if neighbor was visited -> cycle
            * 
    * Topological sort
        * 起始點不重要 但選取的點會影響結果
        * ![](https://hackmd.io/_uploads/ryQ7Zl7D2.png)
        * dfs
            > ![](https://hackmd.io/_uploads/SyPxbxQv3.png)


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:
    * ![](https://hackmd.io/_uploads/rJudRZ8D2.png)

        * **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**
        > ![](https://hackmd.io/_uploads/rJoq9gXPn.png)
* **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
    * ![](https://hackmd.io/_uploads/B1RX6gmwh.png)
    * 最長路徑 - weighted DAG
        * 將所有weight都加上負號 用topological sort找最短路徑
            >負越多 -> path越長

* **Bellman-Ford’s Algorithm**
    * Negative Weights 
        * 因為Dijkstra不能有負邊
        * disTo\[s\] = 0 
        * 所有連接到s的node V => disTo\[V\] = ∞
            * relax 全部的 V
                > ![](https://hackmd.io/_uploads/HkxrQgfXD3.png)
        * ![](https://hackmd.io/_uploads/r1oEAWmvn.png)
        * 依照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**
![](https://hackmd.io/_uploads/HkF0CgQwh.png)



Lecture 12 - NP completeness
---
* **NP-Complete & 演算法難度(自主學習!!!會考!!!)**
    >intractable -> **2^n**
* **Class:**
    1. 已被證實可以解的![](https://hackmd.io/_uploads/Sk_uyQ8vh.png)
    2. 已被證實是難解的![](https://hackmd.io/_uploads/H1itJXIvn.png)
    3. 已被證明無法解決的問題![](https://hackmd.io/_uploads/Sy9q17Uvh.png)
    4. 尚未被證明是難解的 不知道有沒有解 (可能是我們不夠聰明)![](https://hackmd.io/_uploads/rJSoyXLwh.png)
    * **Class 4** EX:
        * SSP
            * 2^n -> n個數字 有或沒有(1 or 0)
            * ![](https://hackmd.io/_uploads/Byn--XID2.png)
        * TSP
            * 2^n
            * ![](https://hackmd.io/_uploads/Sk9QQXIP3.png)
        
* **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糾結的點:
        > ![](https://hackmd.io/_uploads/BkRcBmIP3.png)

        
* **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
    * ![](https://hackmd.io/_uploads/SkP49lIPh.png)
    * 把剛才算的fib(0) fib(1)...等等記錄起來 之後直接查找
        * top-down (recursive) 大問題拆小處理再加起來
    * ![](https://hackmd.io/_uploads/B1-UseUvn.png)
        * bottom-up (iteration) 小問題丟給大問題處理
    * ![](https://hackmd.io/_uploads/BJ10olID3.png)
* **Rod Cutting Problem**
    * 把大問題漸漸拆成小問題 用DP讚讚
        * ![](https://hackmd.io/_uploads/BkQB1ZLPh.png)
    * 教授表示他喜歡iteration版本比較簡單
        * ![](https://hackmd.io/_uploads/B17mkbUv2.png)

* **Matrix Chain Multiplication**
![](https://hackmd.io/_uploads/S1fwFfLD3.png)
    * **計算1-3的最小成本 => 兩種情況**
        ![](https://hackmd.io/_uploads/SyxXttMLwh.png)
    * **這裡是3種情況 (p.s老師算錯中間那個應該要是3x7x8)**
        ![](https://hackmd.io/_uploads/HJYuqfLv2.png)





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



