# Select Topics

## Miss something in CLRS

### Subset sum in DP


if (v_i <= w) then // 判斷當前附載種能否選擇當前物品
    v[i, w] = max(v[i-1, w], v_i + v[i-1, w - v_i]); // 若可以則比較
else // 若附載不足則依上回合最佳解代入
    v[i, w] = v[i-1, w];
// 後者 v[i-1, w - v_i] 代表找剩下 w - v_i 空間中 前 i- 1 物品選擇之最佳解

### 2 n-bit multiplying


1. 以 $(x_{1} + x_{2})(y_{1} + y_{2}) - x_{1}x_{2} - x_{2}y{2}$ 求 $x_{1}y{2}, \ x_{2}y_{1}$
2. 如此乘法只需 3 次

## NP

### Some def.



### What is SAT problem ?


[Proof about SAT](https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem)

### Prove 3 SAT is NPC

1. Verify it as NP $O(n)$
2. Reduction from SAT to 3 SAT $O(nm)$
* 轉換問題
* 轉換過程為 polynomial time computable
* 彼此相互等價


* n : the number of clause
* m : the number of new literal





### Prove Clique is NPC





### Prove Vertex cover is NPC

Vertex cover 為一組點集使得每條圖中的邊皆有被碰觸到


* 原構成 Clique 之點集，將其圖 G 求反圖時，將圖中所有點與此點集取差集時，即為圖中之 vertex cover



### [Prove Hamilton path is NPC](https://youtu.be/4r78NtOnWWA)





* 中間點個數為 clause 個數
* 從上走左為 true，走右為 false (可互換)，繞完中間繼續往下走
* 在群尋訪中間 vetrex 時，會間接確認此 clause 是否 satisified
* 整體尋訪是 polynomial * polynomial 仍為 polynomial

### [Prove Hamilton cycle is NPC](https://youtu.be/M0dV30qWPaw)

* 證 NP 即是讓 H.C. 可以在 polynomial time 時間下能夠 verify 能否成為 H.C. (yes/no)
* 而證NP-Hard，跟 Hamilton path 類似，也是用 3 SAT reduce to H.C.
* 依據 3 SAT 建 H.C.
* 跟 H.P. 不同在於進串聯 vetrex 至最後點後會有多一條 edge 至剛起始點的下條路


-------------------------------------------------------------------------------

* 用 Hamilton path reduce to hamilton cycle



### [Subset sum problem](https://youtu.be/83VZvAo8Hy8)

* 用 SAT reduce to subset sum


### Check the graph is H.P. or not


題目問說，找到一條 H.P. 且 x 不為起始點或終點

1. 首先新增 a, b 兩點且與 x 點以外之點相連
2. 再新增 s, t 分別與 a, b 相連
3. 則可得到以 s 或 t 為起點能構成 H.P. 之情形

* 證明此演算法正確性，不因新增 a, b 兩點而使原本不構成 H.P. 的圖成為 H.P.
* 可以發現若先尋訪 a, b 再連回途中點完成 H.P. 會漏掉 s, t，則可發現不能在最後過程前先連 a, b
* 而新增 a, b, s, t 不影響原圖構成 H.P.，因 s - a - G - b - t 構成 H.P.，則原圖 G 必也為 H.P.


## Approxiamtion Algorithm

避免 time complexity 過大，選擇 suboptimal solution

結果有可能為最佳，也有可能不是


### Approximatopn ratio



e.g. :
2-approximation algorithm 會保證不比求最大值 * (1/2) 小
不比求最小值 * 2 大
而 1-approximation 則是 optimal solution


### Minimum vertex cover

2-approximation algorithm

1. 從援途中挑與 u, v 連接之邊，並移除與之相聯邊
2. 直到無法挑邊為止
3. 所相連邊之點，即為存在 minimum vertex cover 之集合


上方為 2-approximation algorithm 下方為最佳解


time complexity 為 polynomial
1. adjacency matrix : $O(V + E)$
2. Priority queue : $O(ElgE + V)$


### How to prove approximation algorithm

1. 確認其演算法在 polynomial time 可完成
2. 其演算法得出結果是正確的
3. 相較於最佳解，能保證不低於或高於其解 2 倍差

$C^{*} \ : \ optimal \ solution \ , C \ : \ approximation \ solution$


### Traveraling-salesaman problem

從圖中找 Hamiltionian cycle 且其 cost 為最低


* 如果 P != NP，則無法在多項式時間內找到 General TSP 之 Algorithm



### Set covering problem


e.g. 給 $U = \{1,2,3,4,5\} S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$
則可以找到 $\{\{1,2,3\},\{4,5\}\}$ 此子集為最小覆蓋之集合

----------------------------------------------------------------------

<h4>Vertex cover can reduce to set covering problem</h4>

大致簡介證明，非完整證明

time complexity for reduction is $O(mn)$


#### Greedy algorithm for solving set covering problem


## String matching

### Def


### String-matching automata


### Algorithm



## Computational Geometry

### Convex hull

Goal : 找最小凸多邊型
1. 首先找起點，選擇 y 最小，若發現有不只一點，則多觀察並選同時具 x 最小
2. 使用 crossed product function 檢查 o, a, b 三點
3. 得出值為正，則選擇此點 a，若得出為負，則放棄此點 a

$p_{1} = (x_{1}, y_{1}), p_{2} = (x_{2}, y_{2})$
$det\begin{pmatrix}x_1&x_2\\y_1&y_2\end{pmatrix}$

* ==cross product > 0，clockwise== // 選擇此者
* cross product < 0，counter clockwise


### Closet pair problem

核心思路 : Divide and Conquer
將圖終點分為左半和右半，分別解出兩邊最小 $min_L, min_R$ 間距後，
以其中最小值 $d = min(min_L, min_R)$ 選擇，依此來比較左右半邊是否有小於此間距之解

當 n < 3，直接解 $O(1)$
$n >= 3$，再用此演算法
$T(n) = 2T(n/2) + O(n)$, time complexity : $O(nlgn)$