# 演算法 研究所讀書筆記
[TOC]
## 大綱
| Unit | 考古程度 | 熟練程度 | 備註 |
|:----------------------:|:--------:|:--------:|:----:|
| Introduction | ★☆☆☆☆ | ✓✓✓✓✓ | |
| Time Complexity | ★★★★★ | ✓✓✓✓✓ | |
| Recurrence | ★★★★☆ | ✓✓✓✓✓ | master thoerm |
| Dynamic Programming | ★★★★☆ | ✓✓✓ | |
| Graph Algorithm | ★★★★★ | ✓✓✓✓✓ | |
| Computational Geometry | ★★☆☆☆ | ✓ | |
| NP Complete | ★★★★★ | ✓✓✓ | |
### 準備
[x] Time Complexity
> Master Thereom必備！畫tree也是另種方法，求時間複雜度有很多種方法，我覺得每個都很重要，所以建議大家都要讀一下～
- [x] Recurrence（Divide and Conquer）
> 遞迴對於一個programmer也不是件簡單的事情，當然，邊界條件一定要定義清楚，清大常會叫你手寫出遞迴psuedo code，所以在讀這邊的時候要記得自己寫寫看遞迴code。
- [x] Dynamic Programming
> 除了KMP那邊需要多花時間去著墨，其他都是將recurrence的問題化簡，而產出的code，所以難度沒有太高。建議演算法的code也要會，自己最好可以自己默寫一遍。能在電腦上Compile當然是更好！
- [x] Graph Algorithm
> 五顆星！每個的演算法時間都要知道，哪個演算法有啥限制（例：不能有負環等）也要知道，並且要知道為什麼會有些限制，曾經考過證明。
> 1. BFS、DFS
> 2. Minimum Spanning Tree
> 3. Shortest Path Problem
> 4. Flow Network
> 5. Topological Sort
- [x] Computational Geometry
> 不是很重要...
- [x] NP Complete
> 要練習Reduction的話找清大考古題，要練習觀念的話找交大考古題，這兩所的考題方向不同，清大會要求你有能Reduce的能力，交大要你觀念清晰，並且知道哪些是已知的NPC問題。台大資工今年也有考一題NP Reduction，不過我直接沒寫😔
:::spoiler

:::
## 第一章節(time complex)
### Asymptotic Algo

Here we need to know. When we slove the ploblem we use the Algo.

* 1.And the Avg time we use to slove is the θ(n) tigh bu,

* 2.The worst we use to slove is O(n)

we also call it lower bum
* 3.The best time to slove is Ω(n)

we call it upper bum

____

Here have an cloums

| Slove time | simpsize | growth oder | name |
| --------------- | --------- | ----------- | ------------- |
| Wost time | f(n)=O(n) | g(n)≥f(n) | upper bound ⇓ |
| Avg time | f(n)=θ(n) | g(n)=f(n) | tight bound |
| Best time | f(n)=Ω(n) | g(n)≤f(n) | lower bound ⇑ |
| Stric Wost time | f(n)=o(n) | g(n)>f(n) | upper bound ⇓ |
| Stric Best time | f(n)=o(n) | g(n)<f(n) | lower bound ⇑ |

___
We need to find the best sloution we also call
it tight boum and sita(θ(n))

* pinck the upper(O) to forward the (θ) (the upper go down )

* pinck the lower(Ω) to forward the (θ)(the lower go down)


### Calculate E.g
Here we need to find the tight bound
* Tower of Hanoi (河內塔)
*

## 第二章 Recursion(遞迴)
### info
The recusion is the function call it self (we also call it to find the)

**Fibonacci**


It is really good sample to let you know
here we use the **python**

 def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

And we

## CH3 Divide-and-Conquer
- When we slove an problem we is to hard to slove maybe we can dive it to subproblem
- Often gives significant, usually polynomial, speedup
### step of the Dc use
- Step 1. Divide list to two halves, A and B
- Step 2. Sort A using Merge Sort
- Step 3. Sort B using Merge Sort
- Step 4. Merge sorted lists of A and B

## CH4 Sort

## DP
### Gready
* we need to find the optimal algo(global maximal)
# greedy algo
## 1 Minimum Spanning Trees
### Spanning Tree
- 定義
- S = (V, F)為G的一個Spanning Tree且S滿足
- 自F’中任取一邊加入S中必形成Cycle
- 在S中任何頂點對之間必存在一唯一Simple path
- 性質
- 若G 不連通則G無Spanning Tree
- G中的Spanning Tree不只一個
- 同一G中的任二個不同之Spanning Tree不一定有交集的邊存在
### Minimal Spanning Tree
- 定義
- 

- 在G 的所有Spanning Tree中，具有最小的邊成本總和者。
可求MST的演算法如下

#### Prim’s Algorithm：
- 從一個點出發( U, V-U )，像Dijkstra，由擴張樹的某一頂點與其它頂點的所有邊中挑選出具最小值者，不允許有迴路，O(n^2)，使用資料結構Heap優化，O(ElgV)。
- 

#### Sollin’s Algorithm：
- 以merge的概念實作，剩一棵樹結束

**皆是greedy algorithm。**

#### Kruskal’s Algorithm
- 概念
- Kruskal演算法是一種用來尋找最小生成樹的演算法，是greedy演算法的應用。Kruskal演算法是以增加邊的觀念做為出發點。首先將所有的邊，依照權重的大小排序。再來依序加入權重最小的邊，如果造成cycle時，則必須捨棄，直到增加了n - 1條邊為止(假設有 n 個節點)。Kruskal演算法在圖中存在相同權值的邊時也有效。
- 步驟
- 選擇：由spanning tree的所有邊中，挑選出具最小值者**(不允許有迴路)**。
重複直到下列任一條件成立為止
(n-1)個邊已挑出 //n是頂點的個數
無邊可挑，若 |F| < n-1，則無spanning tree
複雜度分析
建邊權重的heap : O(E)
取得並刪除最小權重的邊(u,v) : O(logE)
需偵測取得的邊是否構成cycle，使用set operation操作，同一集合為同set
union(u,v) : O(1)
Find(u) : 花O( a(m,n) ), 逼近O(1)
每回合最多花O(logE)
因此Kruskal’s Algorithm complexity = O(E) + O(ElogE) = O(ElogE)
證明
手法為cut-and-paste
假設最小權重的邊E不在minimum spanning tree T中
在T中加入E會形成cycle
因此拿掉一個比E權重大的邊，形成權重較小的T’，矛盾而得證

## SEARCH