---
# System prepended metadata

title: Select Topics

---

# Select Topics

## Miss something in CLRS

### Subset sum in DP

![](https://i.imgur.com/wIN8dMn.png)

``` c 
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

![](https://i.imgur.com/vXaN0qn.png)

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.

![](https://i.imgur.com/sglaJL2.png)

![](https://i.imgur.com/XKcLWQ3.png)

### What is SAT problem ?

![](https://i.imgur.com/t6kRHYt.png)

[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
* 彼此相互等價

![](https://i.imgur.com/ab5F3iQ.png)

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

![](https://i.imgur.com/zxJusoq.png)

![](https://i.imgur.com/lK1D5ch.png)

![](https://i.imgur.com/p7SdKgm.png)

![](https://i.imgur.com/3LzHd1y.png)

### Prove Clique is NPC

![](https://i.imgur.com/cSVJe4Y.png)

![](https://i.imgur.com/U3n7Lg5.png)

![](https://i.imgur.com/pXWCM0E.png)

![](https://i.imgur.com/gzbTR4t.png)

### Prove Vertex cover is NPC

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

![](https://i.imgur.com/BXaTj1Y.png)

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

![](https://i.imgur.com/o1Xq7Dj.png)

![](https://i.imgur.com/6aBKzKl.png)

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

![](https://i.imgur.com/DFnkKSZ.png)

![](https://i.imgur.com/6fwqLFd.png)

![](https://i.imgur.com/EdZmOzl.png)

![](https://i.imgur.com/Fp6A1FF.png)

* 中間點個數為 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 至剛起始點的下條路

![](https://i.imgur.com/FiTXGR8.png)

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

* 用 Hamilton path reduce to hamilton cycle

![](https://i.imgur.com/UXAMBnl.png)

![](https://i.imgur.com/dDDS2kr.png)

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

* 用 SAT reduce to subset sum

![](https://i.imgur.com/YE6nfkY.png)

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

![](https://i.imgur.com/2p4PdMF.png)

題目問說，找到一條 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.

![](https://i.imgur.com/LMWu2l2.png)

## Approxiamtion Algorithm

避免 time complexity 過大，選擇 suboptimal solution

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

![](https://i.imgur.com/KhTMZ6x.png)

### Approximatopn ratio

![](https://i.imgur.com/My6oNO1.png)

![](https://i.imgur.com/gzAjxIr.png)

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

![](https://i.imgur.com/XUPPNg2.png)

### Minimum vertex cover

2-approximation algorithm

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

![](https://i.imgur.com/qqJOqYL.png)

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

![](https://i.imgur.com/F8786um.png)

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

![](https://i.imgur.com/gxdbi2W.png)

### How to prove approximation algorithm

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

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

![](https://i.imgur.com/kFE0Vn0.png)

### Traveraling-salesaman problem

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

![](https://i.imgur.com/yepW5Dx.png)

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

![](https://i.imgur.com/qWOXqtV.png)

![](https://i.imgur.com/xV1qtv2.png)

### Set covering problem

![](https://i.imgur.com/OAuXjwF.png)

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)$

![](https://i.imgur.com/d6TrTah.png)

#### Greedy algorithm for solving set covering problem

![](https://i.imgur.com/r79AJc9.png)

## String matching

### Def

![](https://i.imgur.com/w03kpRM.png)


### String-matching automata

![](https://i.imgur.com/dTbuHa8.png)

### Algorithm

![](https://i.imgur.com/60EjKyi.png)

![](https://i.imgur.com/7ab8j63.png)

##  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 

![](https://i.imgur.com/WB1Pzs5.png)

### 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)$