# Final Exam - Algorithm
## [Q01]
### What is the sorting problem? What are typical sorting algorithms and their key ideas? How do you analyze the complexity of sorting algorithms?
* Sorting problem是一個計算問題，輸入是一個大小為n的數列$A$包含了<$a_1$, $a_2$, $a_3$,...$a_n$>，輸出則是一個排序好的數列$A'$其中的element <$a_1'$, $a_2'$, $a_3'$,...$a_n'$>的關係為$a_1'$<= $a_2'$<=$a_3'$<=...<=$a_n'$
* sort演算法可以分成比較式的演算法常見的有insertion sortquick sort, merge sort, heap sort等。
* sort有兩個性質
1. In place：在地排序，不需要使用額外跟長度有關的外部記憶體
2. Stable：具有相同值的元素，在排序前的相對位置會跟排序後的相對位置一樣
* **Insertion sort是一個漸進式的策略，可以看做我們將未排序數列中的數字，一一插入已排序數列中，並且使插入後的數列仍是已排序數列。可以使用Loop invariance證明其正確性。Insertion sort是一個Stable sort；也可以有In place的特性**
* 時間複雜度：總共要插入n個數字，每次插入需要比較的次數最多就是已排序數列的長度，因此worst case需要比較的次數為$1+2+3+...n-1$，因此時間複雜度為$O(n^2)$
* **Merge sort會將待排序數列分成兩個子序列，並且持續此動作直到子序列的大小為0或1，接著將排序好的子序列合併成一個新的有序數列，直到回復成最初待排序列的長度。Merge sort主要是利用Divide-and-Conquer-and-combine的概念去解決sort problem，將大問題分成小問題，並將小問題解決後合併小問題的解去解出大問題。Merge sort不是一個In place的演算法，是一個Stable sort。**
* 時間複雜度：可以將問題寫成$T(n) = 2T(\cfrac{T}{2})+n$，其中的n為combine的成本，由於必須比較每個子序列中元素的大小關係，因此最多需要比較n次，計算成本集中在combine上，**藉由master theorem**可以得出$T(n)=nlog(n)$
* **Quick sort會挑選數列中的一個數作為pivot，並且藉這個pivot將數列分成兩個子序列，其中一個子序列會都小於這個pivot，另一個則會都大於這個pivot。並且跟Merge sort一樣會持續此動作到子序列長度為1或是0，最後再合併起來。Quick sort是一個In place的演算法，但不是一個stable sort，因為相同值的元素可能因為被選為pivot而使其相對位置發生改變。**
* 時間複雜度：Quick sort best case的情況是每次挑選出pivot都剛好將數列分成兩半，也就可以寫成$2T(\cfrac{T}{2})+n$，因此best case的時間複雜度為$O(n)=nlog(n)$。而Worst case的情況則是每次都剛好分割成了n-1跟1的情況，也就是可以寫成$T(n)=T(n-1)+T(1)+n$，時間複雜度為$O(n^2)$。Average case的部份我們可以使用random variable的概念去證明，證明的結果average case的時間複雜度會為$O(n)=nlog(n)$。我們可以跟merge sort做比較，可以發現merge sort的成本都集中在combine的部分，而quick sort的成本反而是集中在divid-and-conquer，也就是將數列藉由pivot分成兩部分的這個步驟，反而combine沒有任何的成本。
* **Heap sort分成兩個步驟。第一個步驟要先建立Max-Heap，此資料結構是一個complete binary tree，特徵是父節點的值會大於等於子節點的值，建構的方式為建立一個complete binary tree並且從最後一個non-leave-node進行max-heapify直到root為止，Max-Heap建立完成；第二個步驟是將此Max-Heap中的root與最後一個leave node交換位置並將Heap的node數減一，之後由下而上進行Max-Heapify，維持Max-Heap的結構。執行此步驟直到Heap的size為1。Heap sort是一個In place的演算法，但並不是一個Stable sort，原因是在root跟leave-node交換後Max-heapify時相對位置可能產生變化**
* 時間複雜度：Heap sort的分析可以分成三個步驟。第一個是建立complete binary tree也就是最初的heap需要$O(n)$；第二個則是從最後一個non leave node到root進行max-heapify，每次max-heapify最多需要$log(n)$次的比較，因此需要$O(n/2*log(n))$也就是$O(nlog(n))$的時間複雜度；第三個步驟是將Max-Heap中的root與最後一個leave node交換直到node size變為1，此步驟需要執行n-1次並且每次都需要對root進行一次max-heapify，總共需要得時間複雜度為$O((n-1)*log(n))$也就是$O(nlog(n))$。綜上所說Heap sort總體的時間複雜度為$O(nlog(n))$。
* 以上的sort都是compare sort，因此時間複雜度最低為$O(nlog(n))$，若還想降低時間複雜度我們需要額外資訊。
* **Counting sort在知道 n 個數字以及他的值分布的情況下，比如說我們知道這些數字的分布都在1~k，首先，我們先建立一個大小為k的陣列來計算出現個數，然後從原始陣列的後端讀取數並且將陣列中對應到的count數加一，最後查詢累計數字表並將此數字根據出現次數由後往前擺放。(從後面掃是為了要保持 Stable 特性)**
* 時間複雜度：統計：O(n)，累計：O(k)，填入：O(n) => O(n+k)

* **Radix sort從低位數開始排，用 Stable 的 sorting 排序。像是 counting sort、insertion sort、merge sort**
* 時間複雜度：O(d(n+k))
---
## [Q02]
### What is the dynamic programming (DP)? Please compare DP and divide-and-conquer. Please give an example to illustrate DP development.
* DP是一個解決問題的技巧，他將一個較難較複雜的問題拆分成很多**重複**的子問題，並且用空間換取時間的概念，將已經處理過的子問題解儲存起來，避免重複計算。
* 當我們要確認一個問題是否能用DP解時，我們需要確認這個問題是否有最佳化子結構(optimal substructure)，最佳化子結構的定義是，當一個解是一個大問題的最佳解，這個解必定由子問題的最佳解組合而成。
* DP跟divide-and-conquer的相同之處是都是將大問題分解成小問題，再由小問題的解結合出大問題的答案。但DP由於有記憶重複問題的特性，因此在處理大量重複子問題時會更有效率。因此我們可以藉由觀察overlaping的程度來決定要使用哪種方式解決問題。
* 一個DP algorithm會有四個步驟
* 1. 描述此問題的最佳化子結構
* 2. 由於問題的最佳解可能不唯一而且構造解無法計算，因此我們要將解構造的問題轉換成值的計算。並且定義出該值的遞迴式。
* 3. 接著用bottom-up或是top-down的方式解出問題及子問題的解，在解的同時要記錄下來。
* 4. 用計算出的值回推最佳解
* **LCS(Longest common Subsequence)是一個計算問題，輸入是兩個字串x,y分別有m跟n個字元，輸出是一個x,y共同的子字串，長度要是最長的，子字串不用連續但要依序。**
* Naive：若$n>=m$，則時間複雜度為$O(n*2^m)$，因為有$2^m$種的可能需要驗證每次的驗證時間為O(n)。
* 使用DP：
* 1. Optimal Substructure：如果一個長度為k的字串Z是x,y的LCS，那如果$x_m=y_n=z_k$，$Z$是由$X_{m-1}$與$Y_{n-1}$的LCS與x_m組合而成；若只有$x_m=z_k$的情況則$Z$就是$X_m$與$Y_{n-1}$的LCS；反之，若只有$y_n=z_k$的情況則$Z$就是$X_{m-1}$與$Y_{n}$的LCS。
* 2. Recursive Formula：建立一個$m*n$的table名為c，$c[i,j]=0$當$i$或$j$為0；若$x_i=y_j$的情況之下$c[i,j]=c[i-1,j-1]+1$；若$x_i\not=y_j$則$c[i,j]$會等於$c[i-1,j]$或$c[i,j-1]$兩者中較大的那個。
* 3. 接著用bottom_up的方式填入數據
* 4. 獲得了LCS length的最大值，使用table的數據回推最佳解。
* 5. 複雜度分析：
* Compute Time：$O(m*n)$
* Construct Optimal solution：$O(m+n)$
* Space：$O(m*n)$->$O(n)$
* Example：
* X = ABCB<br>Y = BDCAB<br>LCS(X,Y)=BCB

| | $Y_j$ | B | D | C | A | B |
| ----- | ----- | - | - | - | - | - |
| $X_i$ | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 1 | 1 | 3 |

* 額外Example：Matrix-chain multiplication、Optimal polygon triangulation problem
* Matrix-chain multiplication：
* 矩陣列乘法的純量乘法數最佳化問題是一個計算問題，他的輸入是一串n 個矩陣的相乘，輸出是一個括括號的方法，來讓整個純量乘法數是最小的。
* Optimal polygon triangulation problem：
* 凸多邊形三角化問題是一個計算問題，他的輸入是一個n 個點序列的多邊形，輸出數要將多邊形切成多個三角形，再點之間連線，並使他的權重總合為最小。
---
## [Q03]
### What is the greedy method? Please compare DP and greedy algorithm. Please give an example to illustrate greedy algorithm development. How do we analyze the bound of a greedy algorithm?
* Greedy method是一個貪婪的策略，我們面對選擇時總會選擇當下的最好的選項。
* 相較於DP需要計算大量的子問題，需要確認每種子問題的組合且需要memorization，greedy method只需要找到每個選擇的local optimal solution來組合成全域最佳解，因此不需要記憶。
* 但是俗話說的好「貪圖一時快活，必然留下隱禍。」，greedy method不一定可以找到每個問題的最佳解，若一個問題可以發展出greedy algorithm，也就是可以用貪婪的策略找到最佳解，則必須符合下面兩個條件。
* 1. Optimal Substructure：跟Dp相同，當一個解是一個大問題的最佳解，這個解必定由子問題的最佳解組合而成。
* 2. Greedy-choice property：全域的最佳解可以由local的最佳解組合而出，
* 可以發現Greedy method只是找出DP的其中一種組合，因此事實上能夠使用Greedy algorithm解的問題，其實都可以使用DP來解。但Greedy algorithm在解決此種問題時更加有效率且不需要額外的記憶體空間。
* **Activity selection也就是藝人跑通告問題是一個計算問題，輸入是一個有n個活動的集合A，每個活動包含了開始時間、結束時間，輸出為一個時間不互相衝突的活動集合，活動數要最多。**
* 1. Optimal Substructure：若S為A集合內的最佳解，那對於任意在A集合中的活動i而言，若i$\notin$S則S同為A去掉i集合的最佳解；若i$\in$S則S去除i會為A去掉所有與i時段重疊活動集合的最佳解。
* 2. Greedy-choice property：選擇最早結束的活動當做貪婪的策略，因為如果一個集合中的最佳解S中不包含集合中最早結束的活動l，我們一定可以把該解的第一個活動k帶換成l，S去掉k加上l也必然是最佳解。
* 既然Greedy method可能找不到最佳解，為何有些問題我們會嘗試使用greedy method來找答案，因為greedy method雖然可能不是正解，但我們可以藉由greedy method找到一個還不錯的解。假設現在 n 個元素，最好的解是k，greedy 與最佳解的距離會在$ln(n)$倍之內，也就是$k*ln(n)$。我們可以用Set cover problem為例子來證明這個bound。

* 市長蓋小學問題是一個計算問題，輸入是給定一個宇集合U和給定一個點集合的集合S，輸出目標為找到S的其中一個子集合，並且子集合中所有元素的聯集為U，子集合的元素個數最小。
$n_{t+1}\le n_t-\frac{n_t}{k}=n_t(1-\frac{1}{k})$

* 額外Example：Maximum sum selection、Data transmission：Huffman encoding、Task scheduling problem
* Maximum sum selection：
* 最大合選擇問題是一個計算問題，輸入是n 個數字和一個值k，輸出為n 個數字中的k 個總合為最大的數。作法只要跑一個k 迴圈，每一輪都挑最大的值出來即可。
* Optimal polygon triangulation problem：
* 凸多邊形三角化問題是一個計算問題，他的輸入是一個n 個點序列的多邊形，輸出數要將多邊形切成多個三角形，再點之間連線，並使他的權重總合為最小。
* Task scheduling problem
* 任務排程問題是一個計算問題，輸入為給定一個假設都是單位時間的任務，每一個都有他的死線和懲罰，要輸出一個排程來最小化所有沒有在死線內的任務的懲罰。
---
## [Q04]
### What is the minimum spanning tree (MST) problem? What are typical algorithms for MST problems and their key ideas? How do you analyze their complexities?
* Minimum spanning tree，也就是最小生成樹問題是一個計算問題。他的輸入是一個有權重的無向圖G=(V,E)，輸出是最小生成樹，輸出為cover所有的Vertices的Subset T，而且所有邊的權重總合為最小的。
* Tree的定義是無迴圈且所有節點相通的圖。
* 這個問題我們可以使用greedy algorithm去計算，那我們使用greedy algorithm有兩個前提
* 1. Optimal substructure：若T為G的MST，那我們選T的任意一條邊將G分成G1=(V1,E1)和G2=(V2,E2)，這條邊也會將T分成T1跟T2。則T1、T2分別也會是G1、G2的MST。這個我們可以利用反證法證明其的正確性。
* 2. Greedy choice property：若T是G=(V,E)的最小生成樹，若有一個邊k(u,v)將T切成A和V-A且k為連接A和V-A的最短邊，則(u,v)屬於T。此可以用反證法證明其正確性，假設這個最小邊不在T中，那我們可以將T之中連接A和V-A的邊換成k形成$T'$，這樣$T'$的權重合會小於$T$，和假設的$T$為G的MST矛盾。
* MST的greedy algorithm有兩種比較經典，一個是Prim另一個是Kruskal，Prim的概念是一顆種子慢慢成長為一顆完整的樹；而Kruskal的概念則比較像一片森林然後樹根慢慢相連，最後全部的樹變成一棵大樹。更細節的演算法如下：
* Prim的演算法會先隨機選擇一個點當作樹的種子，接著尋找身邊最有利的環境繼續發展，也就是從跟目前樹相連新節點中找到的最小邊的那個節點，並且將該新節點加入成為樹的一部分，持續到所有節點都加入這棵樹裡面。
* 時間複雜度：Prim演算法在初始化所有節點時會花費$O(V)$的時間，加入節點到樹裡面的過程中會先找到相鄰的最小邊，如果使用Heap的結構的話這個步驟需要$O(log(V))$，總共會加入V個節點，因此該步驟的時間複雜度為$O(Vlog(V))$，最後一個時間複雜度則是當我們加入節點後要去更新所有跟樹相臨點的權重，這個更新的總次數為$O(E)$，每次更新也都會用到heap的結構因此時間複雜度為$O(V)$，因此最後一個步驟的時間複雜度為$O(Elog(V))$。因此總時間複雜度為$O(Elog(V)+Vlog(V))$。
* Kruskal的演算法會向下俯瞰整座森林並且找到最適合連接的通道，首先我們會將所有邊根據權重排序，並且每次都選擇最小邊，若該邊會造成循環則將這個邊從選擇裡面剃除。持續加入邊直到所有的節點都在這棵樹中。
* 時間複雜度：Kruskal演算法會將邊先進行排序，因此時間複雜度為$O(Elog(E))$。而後面會依序將最小邊加入進樹裡面，但每次都要判斷新的邊是否會造成循環，我們可以使用disjoint set的結構使判斷是否造成循環的時間複雜度為$constant$，總共進行E次，因此該步驟的時間複雜度為$O(E)$。總時間複雜度為$O(E)$+$O(Elog(E))$，也可以直接寫成$O(Elog(E))。
---
## [Q05]
### What is the single-source shortest path (SSP) problem? What are typical algorithms and their key ideas for shortest path problems? How do you analyze their complexities?
* 單源最短路徑問題是一個計算問題，輸入是一個有權重的有像圖G=(V,E)和一個V所包含的特定節點$v_s$，輸出$v_s$到除自身外每個節點的最短路徑。
* 不能有負權重迴圈，也就是一個循環中所有的weight總和必須大於等於0。
* 如果有路徑權重的權重為負的，我們可以使用Bellman-Ford演算法；如果G無負權重路徑，則我們可以使用較為快速的Dijkstra演算法。兩種演算法都會使用到Relaxation(鬆弛)的特性。
* 他的optimal substructure：一個最短路徑的subpath 也會是最短路徑。(反證法假設$w(p_{ik}')=w(p_{ij}')+w(p_{jk})$，若$w(p_{ij}')<w(p_{ij})$則加回去也會是最小，錯誤，反證法得到)
* Relaxation：比較一段路徑加上一個中繼點後是否會會變得比較小，若比較小則更新路徑長度跟過程。如果有一段path是直接從s->t路徑長為l，若在路徑中加上一個額外的點u使path變成s->u->t且路徑長為l'，若l<l'則維持原樣；反之，若l'<l則s->t的最短路徑更新為s->u->t且路徑長為l'，此過程就叫Relaxation。因為SSP的optimal substructure，所以我們可以直接將較短的路徑取代掉原本的路徑。
* Bellman-Ford演算法中，如果有一條shortest path $p=[s, v_1, v_2, v_3, ...]$，那當我們relax第一次的時候就會找到$v_1$，第二次會找到$v_2$，也就是說以次類推一條shortest path的最大可能長度為|V|-1，我們只要relax |V|-1次便可以找到所有shortest path經過的點
* 時間複雜度：由於path會經過最多的節點數是V-1次，每次都會Relaxation所有的邊。因此時間複雜度為$O(|E||V|)$
* Bellman-Ford中的特例：如果graph是Directed acyclic graph(有向的無迴圈圖)，則可以使用topological sort以時間複雜度$O(|V|+|E|)$完成問題的計算。
* 時間複雜度：topological sort的時間複雜度為$O(|V|+|E|)$只要根據sort的順序Relaxation當下節點相鄰的邊即可，Relaxation全部的複雜度為$O(|E|)$。因此整個計算的總複雜度為$O(|V|+|E|)$

* Dijkstra演算法中多了一個限制為不能有負權重，有失必有得，Dijkstra的複雜度也下降了。Dijkstra的概念跟Prim類似，每次都將一個節點加入集合，並且將該點所連到的邊加入邊集合，不像是Bellman-Ford需要Relaxation所有的邊，Dijkstra只選擇relaxation已加入節點相鄰的邊，並且每次都用greedy的策略將邊集合中最小邊所連接的新節點加入。
* Dijkstra的時間複雜度跟使用的資料結構有關，以line array存取資料的話會是$O(|V|^2)$<br> ($|V|^2$:extra min:$O(V)$共V次+relax共E次)；以binary heap存取的複雜度會是$O(|E|log(|V|))$ <br>($Vlog(V)$:extra min:$O(log(V))$共V次+relax$O(log(V))$(維持heap特性)共E次)

---
## [Q06]
### Please formally define all-pair shortest path (APSP) problem. What are typical algorithms and their key ideas for shortest path problems?
* ASSP一個計算問題，輸入是一個有權重的有像圖 G=(V,E)，輸出是對於所有節點對的最短路徑。
* 首先是DP的解法，DP會有四個步驟：
* 1. Optimal substructure：
* 先定義$d_{ij}^{(m)}$為i經過最多m步到j的最短路徑。如果$d_{ij}^{(m)}$可以分成$d_{ik}^{(m-1)}+w_{kj}$那$d_{ik}^{(m-1)}$也會是m-1條邊最短路徑
* 2. 建立遞迴式：
* $d_{ij}^{(m)} = min_{1\le k\le n}\{d_{ik}^{(m-1)}+w_{kj}\}$
* 3. bottom-up建立表格：

* 4. 推算出答案：
* 表格中的$d_{ij}$就是i到j的最短路徑。
* 時間複雜度：共要填寫V*V的表格V-1次(最多經過V-1個點)，每次填寫要比較V個點，總時間複雜度為$O(n^4)$
* Floyd Warshell的概念跟DP最大的不同是，DP是一次多一步， Floyd Warshell會一次將一個點加入路徑的考慮中，看加入後路徑會不會變得更短。當我們要回推算出答案的時候可以使用predecessor pointer去記憶路徑。
* 時間複雜度為$O(V^3)$
* 直覺是我們也可以把APSP當作SSP的延伸，直接跑V次的Bellman-Ford，時間複雜度會為$O(|V|^4)$；若是整個graph無負權重的話，我們可以跑V次的dijkstra，時間複雜度會為$O(|V|^3)。很明顯dijkstra的效果會比較好，因此Johnson's algorithm提出了一個方式調整權重使圖中不存在負權重。Johnson's algorithm有三個步驟
* 1. 建立一個新的digraph，在原本的圖加上一個新的虛擬點s，虛擬點s會跟所有原本的節點相連並且權重為0。
* 2. 以s當作起始點做一次Bellman-Ford，計算s到每個點的最短路徑
* 3. Reweight所有的權種，u->v的權重會是(原來的權重+起點的權重-終點的權重)
* 為什麼reweight要這樣設計，不能直接把負權重加到正的嗎？
* 不行，因為每條shortest path的長度不一樣，這樣會造成經過越多節點的shortest path會被加上越多的長度。因此我們的想法應該要是只要起終點不改變，不同路徑的總權值相對大小也應該不變，將原本邊的權重、與起始點跟終點的權重都考慮進去最後將更新的權重訂為(原來的權重+起點的權重-終點的權重)，如此相同起終點的路徑權重和就會因為一加一減不同的只有原來的權重，因此可以保持原本的相對大小關係。
* 時間複雜度分析，執行Bellman-Ford時間複雜度為$O(|E||V|)$，執行V次的dijkstra時間複雜度為$O(V^3)$，總時間複雜度為$O(V^3)$。
---
## [Q07]
### What is order statistics? How do you develop a O(n) algorithm for i-th order statistics?
* ith Order statistics 的定義是在一個有 n 個元素的集合中第 i 小的元素。我們想找到目標的Order statistics這樣的問題就是Selection Problem，Selection Problem 是一個計算問題，輸入給定有 n 個相異元素的集合 A，以及一個數字i，1 <= i <= n，輸出是一個屬於集合 A 的元素 x ，x 會比集合 A 當中的(i-1)個元素還要大。
* Naive：最直接的想法是直接排序，但時間複雜度最低就為$O(n(log(n)))$
* 接著由於他指要求第i個數，我們可以想到找i次最小值也可以獲得答案，如果我們使用array去存取資料，由於每次求最小值要比較n-1次，如果$i=\frac{n}{2}$，複雜度會跑到$O(n^2)$比直覺更糟糕，那如果我們用binary tree存取數字的話，我們每次求最小值只要$log(n)$次，時間複雜度可以降到$nlog(n)$，也勉強只跟直覺打平。
* 因此我們參考quick-sort的想法發展出了rand-select，平均時間複雜度為$O(n)$，但如果是worst case時間複雜度仍有可能跑到$O(n^2)$；因此有人開發了BFPRT-Select的演算法，可以將時間複雜度穩定落在$O(n)$。
* Rand-select跟quick-sort一樣，會隨機挑選一個pivot，並將數列根據這個pivot分成兩個部分A, B，A是小於pivot, B是大於pivot，接著根據|A|還有i決定要從哪個部分繼續做rand-select，若i 剛好等於|A|+1，那pivot就是第i個數字；若i小於|A|+1則從A部分繼續使用rand-select找第i個數字；若大於|A|+1則從B部分繼續使用rand-select找第i-(|A|+1)個數字。
* 時間複雜度分析：
* 如果pivot選得好，每次都將數列分成均勻的兩塊，那遞迴式可以寫成$T(n)=T(\frac{n}{2})+O(n)$，根據master theorem我們可以得知T(n)=n
* 如果pivot選得不好，也就是無法將數列分成均勻的兩個部份的話，極端的例子就是每次都只分成(0, n-1)，如此的話我們就必須執行rand-select n次，每次分類的成本為$O(n)$，因此worst case的情況會是$O(n^2)$
* BFPRT則將pivot的取法做了一些優化
* 1. 首先將所有的數字五個五個為一組，分成$\frac{n}{5}$組
* 2. 找出所有的組別各自的中位數並將組別根據中位數做排序
* 3. 從這些組別中的中位數挑出中位數的中位數，並將其定為pivot
* 其他步驟跟rand-select相同。為何BFPRT會比rand-select來的穩定，是因為我們藉由中位數的中位數的特性，每次都至少可以消除$\frac{n}{4}$個數字，因此我們可以將遞迴式寫成$T(n)=T(\frac{n}{5})+T(\frac{3n}{4})+O(n)$，其中第一個是找中位數的時間複雜度，第二個是剩下部分繼續找的時間複雜度，最後$O(n)$是根據pivot將數字分類的時間複雜度。那我們可以根據master theorem下去計算T(n)的時間複雜度其實就是 $O(n)$。

---
## [Q08]
### What is the formal definition for P, NP, NP-complete and NP-hard? What is Cook’s theorem? Show an example to prove NP-completeness?
* 圖靈機：一個有外部儲存空間的 finite state machine，有一個針頭會讀去外儲存空間的資訊改變finite state machine內部的state。
* P-problem：多項式時間內可解。
* NP-problem：多項式時間可驗證，包含P-problem
* NP-complete：
* 1. NP-complete本身是一個 NP 問題也是一個NP-hard問題
* 2. 所有的 NP 問題都可以在 polynomial time規約為NP-complete。
* 3. 為NP中最難的問題
* NP-hard：NP-Hard是指不確定能否在多項式時間內驗證的問題，NP-hard不一定是NP問題。
* 四者的關係為下圖：
* SAT問題是一個決定性的計算問題，輸入是一個給定的booling function，輸出則是是否有一組變數的值能夠使這個booling function為真。
* 第一個NP-Hard是Circuit SAT，我們所有要證實是NP-complete都要確定兩個點
* 1. 是一個NP問題
* 2. 是一個NP-Hard問題，也就是說可以在多項式時間內將Circuit SAT這個問題轉換成這個問題。
* Cook-Levin證明了3-SAT是一個NP-complete的問題，3-SAT是指一個Conjunctive Normal Form中每個clause裡面都恰好有三個literals，證明的部分有兩個步驟
* 1. 3-SAT是一個NP問題：因為可以在多項式時間內驗證，因此是一個NP問題
* 2. Circuit-SAT問題可以在多項式時間內被規約成3-SAT問題，因此是一個NP-hard的問題
* 先證明Circuit-SAT可以轉換成SAT，再證明SAT可以轉換成3SAT
* 

---
## [Q09]
### What is the network flow problem? Describe the Ford-Fulkerson Algorithm and analyze its complexity. What is the motivation and the key idea of the Edmonds-Karp Algorithm?
* Network flow 是一個有向圖G=(V,E)，邊集合E中的每條邊都具有容量，比如說從u到v的容量我們就表示成c(u,v)且容量必定大於等於0，輸入還會有兩個點，一個為有唯一一個 in-deg 為 0 的點 s，也就是 source vertex，另一個為唯一一個 out-deg 為 0 的點 t，也就是 sink vertex。
* 其中流量會有兩個規則
* 1. Capacity Conditions：管線內的流量必小於容量。
* 2. Conservation Conditions：對於任一一個節點流入的總流量要跟流出的總流量相同。
* Network flow的其中一種問題是Max-flow problem，Max-flow目的是要找輸入的Networt Flow的最大導入流量是多少，也就是有多少的流量會從s流出並流入t。比如說這個network flow的最大流量就為3。其中一種方式是找到Maximum Flow的upper bounds，我們將圖中的點任意分成s端跟t端，我們要找到s端跟t端間容量和最小的值就會是Maximum Flow的Upper bound也就是我們要求的最大導入流量。

* Ford-Fulkerson Algorithm是一個解決max-flow的一個演算法，這個演算法的關鍵是藉由將network flow轉換成residual network，並且不斷嘗試在上面增加流量就是找到一條augmenting path，直到沒辦法為止，我們就可以找到最大的流量了。轉換成residual network的方法是將原本的容量及流量轉換成該向量可以變化的量，比如說v1->(4/12)->v2就可以寫成v1->8->v2, v1<-4<-v2。
* 時間複雜度：這個演算法的時間複雜度很特別，會跟我們的答案「最大流量」有關，由於每次在進行增加流量的時候我們只能保證augmenting path的流量至少唯一，因此如果最大流量為f我們最多要進行f次的遍歷，每一次遍歷都需要花上時間複雜度$O(|E|)$，因此總時間複雜度為$O(|E|*f)$



* 由於Ford-Fulkerson在worst case且最大流量很大的情況下，效率會很糟糕。因此Edmonds-Karp改進了找augmenting path的步驟，原先Ford-Fulkerson只要找到任意一條就行，Edmonds-Karp利用BFS去搜尋residual network最短的augmenting path，並且跟Ford-Fulkerson一樣將augmenting path的流量加到network flow上。
* 時間複雜度：我們先定義一個critical path為每次增加流量中會造成瓶頸的邊。如果有一次u->v是critical path，那下次這條邊出現在augmenting path時，方向一定是相反由v->u且由於每次增加流量時最短的augmenting path是非遞減的，因此一去一回長度就會增加2,由於augmenting path最多經過|V|-1個節點，所以每條邊成為critical path的次數不超過$\frac{|V|-1}{2}$，總共有|E|條邊，因此增加流量的總時間複雜度為$O(|E||V|)$。我們每次使用BFS找最短邊時又要花上$O(E)$，因此總時間複雜度會是$O(V*E^2)$，相較Ford-Fulkerson至少是一個比較容易預估的數值。
---