Algorithms 筆記

# CH1 Analyzing algorithms ## 1.1 Asymptotic notation **Polynomial bounded** $$ f(n)= O({n^k}) $$ $$f(n)為polynomial bounded<=>\lg f(n)=O(\lg n) $$ **Harmonic number** $$ H(n)=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\theta(\lg n) $$ Proof: 利用畫圖f(x)=1/x，積分 **Generalized harmonic number** $$ H_m(n)=1+\frac{1}{2^m}+\frac{1}{3^m}+...+\frac{1}{n^m}=\theta(1) $$ ## 1.2 Recurrence relation **Recursion Tree** **Master Theorem** **Subtitution Method** Step: 1. 猜bound 2. 利用數學歸納法證明 ## 1.3 Amortized analysis * Aggregate(總計的) analysis * Accounting method * Potential method ### 大小常數<對數<多項式<指數<階乘<指指數 ### log*n **Definition:** ![LogStarN.jpg](https://hackmd.io/_uploads/rkpCJ0g76.jpg) log*n是指對n做幾次log運算可使其變成1。 ### 括號排列![括號排列.jpg](https://hackmd.io/_uploads/S1agx_fmT.jpg) # CH2 Divide-and-Conquer **Idea** 遞迴分成三步驟 1. Divide 2. Conquer 3. Combine ## Merge Sort ```cpp= merge_sort(int arr[], start, end){ if(start<end){ mid=floor((end-start)/2); merge_sort(arr[], start, mid); merge_sort(arr[], mid+1, end); merge(arr[], start, mid, end); } } merge(int arr[], start, mid, end){ int p,q; p=mid-start+1; q=end-mid; //創建兩條新array new L[1~p],R[1~q]; //複製原本的array過去 copy(arr[1~p],L[1~p]); copy(arr[mid+1~end],R[1~q]); //開始merge int i=j=k=1; while(i<=p&&j<=q){ if(L[i]<R[j]) arr[k]=L[i]; i++; else arr[k]=R[j]; j++; k++; } if(i<=p) copy(L[i~p],arr[k~end]); if(j<=q) copy(R[j~q],arr[k~end]); } ``` ## The maximum subarray problem **Definition** 給定一個整數陣列A[1~n],其中具有最大元素和之subarray為何? **步驟** 1. Divide:將一個陣列切成兩個子陣列 2. Conquer:計算各自子陣列的maximum subarray 3. Combine:除了比較兩個子陣列的maximum subarray以外，也要找到橫跨兩個子陣列的maximum subarray去做比較，此陣列由中間兩個元素往右與往左延伸計算停在何處可得最大元素何。等於每輪比較三個子陣列。 ```cpp= max_subarray(int arr[]){ 1. 將A[1~n]分成兩個子陣列 B=A[1~floor(n/2)], C=A[floor(n/2)+1~n] 2. 計算B[],C[]之max subarray 3. 計算包含A[floor(n/2)],A[floor(n/2)+1]在內的max subarray 4. 比較此三個max subarray，return最大元素合 } ``` T(n)=2(T/2)+c*n; time complexity=O(nlogn) **DP版** 令r_i表示在A[1~i]中包含A[i]之subarray的最大元素和，則maximum subarray之元素和即為max{r_1,r_2,...,r_n} 因為A[1~i]中含有A[i]之subarray可分成取A[i-1]及不取A[i-1] * $$取A[i-1]，則r_i=r_{i-1}+A[i] $$ * $$不取A[i-1]，則r_i=A[i] $$ 因此， $$ r_i=max(A[i],r_{i-1}+A[i]) $$ ```cpp= max_subarray_dp(arr){ max=A[1]; r=A[1]; for(i=2;i<n;i++){ r=max(A[i],r+A[i]); if(r>max) max=r; } return max; } ``` time complexity=O(n) ## Matrix multiplication **Strassen's method** 詳見講義 **Time complexity** $$ T(n)=7*T(\frac{n}{2})+\theta(n^2)=\theta(n^{lg7}) $$ ## The selection problem 給定n個相異數與k，求其中第k小的數 **Idea** Prune and Search use "median of median" **Algo** ```cpp= Select(A,k){ 1. 將input的n個數分成五個五個一組 O(1) 2. 將每組做Sorting，並求得各組之median(共n/5組) O(n/5) 3. "遞迴"求step2中所得到的[n/5]個median中的median P T(n/5) 4. 求S1,S2, S1收集所有<P之數，S2收集所有>P之數，由此得知P是第x小的數 O(n) 5. 若x<k，則去掉S1與P，形成newA，return Select(newA,k-x) 若x>k，則去掉S2與P，形成newA，return Select(newA,k) 若x=k，則return P T(3n/4)，因為每次至少去掉n/4個數 } ``` **Time Complexity** $$ T(n)=T(\frac{n}{5})+T(\frac{3n}{4})+O(n)=O(n) $$ by recursion tree. ## 2.5 The closest pair problem 在座標平面中給定n個點，其中距離最近的二點稱為closet pair，求closest pair之距離 **Idea** 利用直線將平面分割，切割成較小的子問題 **Algo** ```cpp= Preprocessing: 執行主程式Closest-Pair()之前，先把每個座標點用y座標排序，排序結果置於list-K Closet-Pair(P:plan graph){ 1. 建立一條垂直於x軸之直線L:x=m，這條直線將P一分為二，位於左側的點在集合Left中，位於右側的點在集合Right中 O(1) 2. 遞迴求Left與Right中的closet pair之距離DL, DR，令d=min(DL,DR) 2*T(n/2) 3. 依序從list-K中取出每個Px-m<=d之點，檢查K中緊接著P出現的七個點p'，是否滿足p,p'分屬線的兩側以及dist(p,p')是否<d， O(n) 若滿足，則d=dist(p,p') 4. return d } ``` **Time complexity** $$ T(n)=2*T(\frac{n}{2})+\theta(n)=\theta(nlogn) $$ ## 習題練習 ### Count Inversions of array in O(nlogn) use divide and conquer separate into two equal size subarray sort array and get the information of rank https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/ # CH3 Dynamic Programming 從子問題著手，即解原問題前先將所有可能會參考到的子問題之解全數算出 ## Fibonacci number $$ f_n=f_{n-1}+f_{n-2} $$ $$ f_0=0, f_1=1 $$ **Recursive版** ```= Fib_recursive(n){ if (n==0||n==1) return n; else return Fib_recursive(n-1)+Fib_recursive(n-2); } ``` $$time=\theta(2^n) $$ **DP版** 在計算fn前先將fn-1,fn-2,...求出來，並將結果存在陣列，以便之後直接取值。 ```cpp= Fib-DP(n){ if (n=0 or n=1) return n; int Fib[0~n]; Fib[0]=0; Fib[1]=1; for(i=2;i<=n;i++){ Fib[i]=Fib[i-1]+Fib[i-2]; } return Fib[n]; ``` ### Time complexity $$ T(n)=\theta(n) $$ ### Optimal Structure 當一個問題之最佳解是由子問題之最佳解所構成，則稱此問題具有Optimal solution性質 ## 3.2 The rod cutting problem 假設銷售長度為i的rod可得Pi元，i=1,2,...,n，如何切割一條長度為n之rod可使總收入最大? 假設rn為長度為n時的rod可得之最大收入，則 $$r_n=max(p_1+r_{n-1},p_2+r+{n-2},...,p_n) $$ ### recursive版 ```cpp= rod_cutting(n){ if(n==1) return p[1]; int price=0; for(i=1;i<=n;i++){ tmp=p[i]+rod_cutting(n-i); if(price<tmp) price=tmp; return price; } } ``` #### Time Complexity $$　T(n)=2^n $$ (詳見講義p.67) ### DP版改以Bottom-up ```cpp= rod_cutting_dp(n){ int price[0~n]=0;//price[i]存放長度為i時的最大獲益 int p[0~n];//為length與價格的對應表 for(int i=1;i<=n;i++){ //求length=i時的最大獲益 for(int j=1;j<=i;j++){ tmp=p[j]+price[i-j]; if(price[i]<tmp) price[i]=tmp; } } return price[n]; } ``` #### time complexity $$ T(n)=\theta(n^2) $$ ## 3.3 The 0-1 knapsack problem 令s[i,k]表示在負重為k的情況下選取前i件物品可得的最大收益。 v[1~n]，v[i]代表第i件物品的value w[1~n]，w[i]代表第i件物品的weight 此時s[i,k]可分為 * 取第i件物品，則收益為v[i]+s[i-1,k-w[i]] * 不取第i件物品，則收益為s[i-1,k] 因此 $$ s[n,k] = \begin{cases} max(v[n]+s[n-1,k-w[n]],s[n-1,k]) & \text{n>1} \\ 0 & \text{n<=0 or k<=0} \end{cases} $$ ```cpp= 01_knapsack(n,v,w,W){ let s[0~n,0~W] be a new array for(i=0~W) s[0,i]=0;//沒有物品可以取 for(i=0~n){ s[i,0]=0;//負重為0 for(k=1~W) if(k-W[i]<0)//拿不動第i件物品 s[i,k]=s[i-1,k]; else s[i,k]=max(s[i-1,k],s[i-1,k-w[i]]); } return s[n,W]; } ``` ### time complexity $$ T(n)=\theta(nW) $$ ## 3.4 The Matrix-chain multiplication 給定n個矩陣A_1,...,A_n，其中A_i之大小為P_(i-1)xP_i，以何種括號法計算A1A2...An可使得純量乘積次數最少? $$ 令S[i,j]代表A_i*A_{i+1}*...*A_j所需之最小純量乘積次數 $$ 則 $$S[i,j]=\begin{cases} 0, & \text{if i=j}\\ min_{i\leq k < j}(S[i,k]+S[k+1,j])+p_{i-1}*p_k*p_j, & \text{if i<j} \end{cases} $$ ## 3.5 Optimal binary search trees $$假設w[i,j]=\sum_{k=i}^{j}p_k+\sum_{k=i-1}^{j}q_k $$ $$假設s[i,j]為key值為k_i到k_j之下所建立之OBST $$ 則 $$s[i,j]= \begin{cases} q_{i-1}, & \text{if j=i-1} \\ min_{i \leq r \leq j}(s[i,r-1]+s[r+1,j]+w[i,j]), & \text{if i <= j} \end{cases} $$ ## 3.6 Longerst Common Sequence 給定 X=<x_1, x_2,..., x_i> Y=<y_1, y_2,..., y_j> 令Z=<z_1, z_2,..., z_k >為X與Y之LCS 令S[i,j]=k為Xi,Yj之LCS的長度則可分為三個情況: 1. x_i == y_j，則z_k必=x_i=y_j->s[i,j]=s[i-1,j-1]+1 2. x_i != y_j，則z_k != x_i or z_k != y_j 因此s[i,j]=max(s[i-1,j],s[i,j-1]) ### 變形 1. Longest increasing subsequence 2. Longest common substring 3. Longest palindrome sunsequence 4. Minimum edit distance ## 3.7 KMP 對於一固定Pattern，求出他在文章中出現的所有位置 need O(n) ### prefix function ### failure function 初始值為-1 ## 補充 ### Coin Changing $$有d_1,d_2,d_3,...,d_j種不同的硬幣面額，給定n元，該如何換成同等價值的硬幣，且使硬幣數最少? $$ $$假設money[i]為i元時所能換到的最小零錢數，則可寫出 $$ $$money[i]=min_{1\leq k \leq j, d_k<i}(money[i-d_k]+1) $$ ### 2 way merge 就是一般的 merge sort # ch4 graph algorithms ## 名詞解釋 1. Strongly Connected: A directed graph is called strongly connected if there is a path in each direction between each pair of vertices 2. Weakly connected: A 「directed graph」 is called weakly connect if there is a path between each pair of vertices in the 「underlying undirected graph」 3. Biconnected: A biconnected graph is a connected and 「non-separable」 graph(拿掉任一點，仍為connected) ## 4.1 Breadth-First-Search 每個vertex具有color, color可分為三種 1. white 2. gray 3. black ### time complexity Linked list存edge->O(V+E) adjacency matrix存edge->O(V^2) ### diameter diameter為Graph中距離最遠的兩點。求diameter之步驟: 1. 對任意一點做BFS,其中距離原點最遠的點為v 2. 以v當原點做BFX，其中離v最遠的點之距離即為diameter =>因為做完BFS後的Graph可化為一顆tree，因此可看出在tree上找longest path之問題為linear time可解(然而在一般的圖(具weight)上找longest path卻是np complete) ## 4.2 Depth-first search 除了color之外，還會記錄vertex被發現的時間 ### time complexity O(V+E) ### edge 具有四種edge 1. tree edge 2. back edge 3. forward edge 4. cross edge #### undirected graph 當G為無向圖時，只會有tree edge跟back edge forward edge->back edge cross edge->tree edge #### acyclic graph G不具cycle<=>不會有back edge ### 透過DFS尋找Strongly Connected Componet 1. 先對G做DFS 2. 求G^T，再對G^T做DFS，依照step1求得之v.f由大到小依序選點 ## 4.3 single source shortest path ### Dijkstra 每次都選取目前所能走到的最短路徑之點 Property: 1. Greedy method 2. 圖上不能有負邊 #### time complexity 視用什麼DS存v.d之priority queue而定 1. array: O(V^2) 2. min heap: O(VlogV+ElogV) 3. fibonacci heap: O(VlogV+E) ### Bellman ford 每一輪對圖上的每一條邊做relaxtion(做n-1輪即可得到解) 在DAG上(acyclic)可以linear time的時間找出最佳解，其想法為利用DFS找到topological sort，按照此順序對圖上每一點連出去的邊做relaxtion，則迴圈只須執行一輪 #### DP 可利用DP加速(p.135) #### System difference p.136 ## 4.4 All-pairs shortest path ### Floyd Warshall DP 想法: $$令d_{ij}^{(k)}為由點i至點j且中途只能經過點(1,2,...,k)之最短路徑 $$ $$則d_{ij}^{(k)}可分為 $$ $$1.不須經過點k，則d_{ij}^{(k)}=d_{ij}^{(k-1)} $$ $$2.需要經過點k，則d_{ij}^{(k)}=d_{ik}^{(k-1)}+d_{jk}^{(k-1)} $$ $$因此d_{ij}^{(k)}=min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)})，1\leq k\le n $$ #### time complexity $$\theta(V^3):n個matrix,每個matrix有n^2格，每格O(1) $$ ### Johnson 先調整圖上每邊之weight，使得調完後每邊之weight皆>=0，再對每個點做Dijkstra #### rewieght函數須確保三性質 1. reweight之後的最短路徑會是原圖的最短路徑 2. 若原圖不含負環，則reweight後也不應有負環 3. reweight後每邊之weight皆>=0 #### 步驟 1. 在G中加入一點s，將s與所有的點相連，且weight均為0 2. $$由三角不等式可知，w^{new}(u,v)=w(u,v)+\delta(s,u)-\delta(s,v)\ge 0$$ #### code ``` 1. 加入新點s，與所有點相連，weight=0 2. 利用Bellmanford計算S與所有點之最短路徑 ->O(VE) 3. 對圖上每一邊做reweight ->O(E) 4. 對每個點做Dijkstra ->V*O(VlogV) ``` #### time complexity O(V^2logV+VE) ## 4.5 minimum spannign trees ### Kruskal(邊) Greedy method 先將edge依照weight排序，每次選取最小的edge，如果加入此edge不會形成cycle，則加入，若會，則捨棄。檢查cycle可利用make-set(),find-set() #### Code ``` 1. 將edge依照weight排序 ->O(ElogE) 2. 每次選取最小之edge，判斷會不會形成cycle ->O(E) ``` #### time complexity O(ElogE) ### Prim(點) 令任意一點當作起點，往外擴散，每次選最短的path(類似Dijkstra) ## 4.6 Maximun flow ### Fork-Fulkson greedy method p.150 #### Edmonds-Karp algo 利用BFS加速 ## 補充 ### Permutation(利用DFS之概念) 若有n個元素要做排列，則先考慮第一個要排誰。有n種選擇，利用swap依序把n個元素換到第一個位置，接下去遞迴呼叫剩下n-1個元素做同樣的事情(相當於排列下一個位置)。當已經排列到盡頭時，則印出此排序。 ![image](https://hackmd.io/_uploads/HkdeZftPa.png) ```cpp= void perm(char *list, int i, int n) { int j, temp; if(i == n){ //當遇到盡頭時，印出排序 for(j=1; j<=n; j++) printf("%c", list[j]); } else{ For(j=i;j<=n;j++){ Swap(list[i], list[j], temp); //使list[j]排在第一個位置 perm(list, i+1,n); //遞迴呼叫剩下n-1個元素，排列下一個位置 Swap(list[i], list[j], temp); //記得交換回來。 } } } ``` ## 補充 ### cycle-finding 1. 直接紀錄visit過 2. 龜兔賽跑(Floyd method) * 求奇數長度的cycle 用到 bipartite<=>不具奇數長度cycle 之性質利用BFS進行著色，若無法2-coloring則代表此圖含有奇數長之cycle # ch5 Computational Geometry ## 5.1 Line segment intersection 給定空間中的兩個線段之左右端點，判斷此兩線段是否相交 ### 判斷線段之旋轉方向兩種旋轉方向，clockwise/counterclockwise 將兩個線段視作向量a,b 則det[a b]可用來判斷a至b的旋轉方向 1. det[a b]>0，則a至b為counterclockwise 2. det[a b]<0，則a至b為clockwise 3. det[a b]=0，則a,b為parallel ### 跨坐 1. 若line A之兩端點，一個在line B的右邊，一個在line B的左邊，則稱A跨坐於B 2. 兩條線為相交<=> A跨坐於B且B跨坐於A ### 判斷兩條線相交 ![image](https://hackmd.io/_uploads/r1Q4mKYIa.png =50%x)![image](https://hackmd.io/_uploads/SJj77KFLT.png =50%x) 判斷兩條線相交則須滿足兩個條件 1. det[a b]與det[a c]正負號相反 2. det[d e]與det[d f]正負號相反 ## 5.2 Convex hull(最小凸邊形) https://web.ntnu.edu.tw/~algo/ConvexHull.html **Graham's scan algorithm** 1. 先找出y座標最小之點p，若有多於一點，則取其中x座標最小之點 2. 並將其餘的點，以p當作原點，x軸逆時針旋轉，將碰到的點依序列出 3. 依序確認此點到下一個點之旋轉方向，若需要右轉，則代表此點不適合當作凸邊形之頂點(因為以逆時針方向來看時，凸邊形上的每個點到下一個點之方向都是左轉，不可能有右轉) ![image](https://hackmd.io/_uploads/rJ5PKGKw6.png) ### time complexity 排序: O(nlogn) 依序掃過每個點，且每個點最多只會在stack內進出一次: O(n) Total: O(nlogn) # ch6 NP-completeness ## Complexity class **1. P** 所有可被deterministic algorithm在多項式時間內解決之decision problem **2. NP** 所有可被non-deterministic algorithm在多項式時間內解決之decision problem non-deterministic algorithm包含兩步驟 * Guessing: 先猜出一個可能的解 * Veritfication: 驗證此解是否正確 **3. NP-hard** 難度大於等於NP的集合(可以等於NP) **4. NP-complete** 屬於NP也屬於NP-hard的集合，即NP當中最難的那一群想要證明一個問題為NP-complete，則需要證明兩性質 * 此問題屬於NP * 存在一個NP-complete的問題難度小於等於此問題 ## 著名的NP-complete問題 **1. The 3-CNF satisfiability problem(3-CNF-SAT)** 給定一個Conjunction Normal Form，其中每個clause皆具有3個literal，則是否存在一組truth assignment使得此CNF為true **2. Find Clique** 3-CNF難度小於等於Find_Clique **3. The vertex-cover problem** vertex cover: vertex之集合使包含所有的edge Clique難度小於等於vertex cover(也可用來證明independent set, dominatin set) **4. The Hamiltionian-cycle(path) problem** 省略證明 **5. The traveling salesman problem** Hamiltion cycle難度小於等於traveling salesman **6. The longest-path problem** Hamiltion path難度小於等於the longest-path ## 6.3 Approximation algorithms 當一個問題Q之decision version已經被證為難題(NP-complete)後，則欲求其最佳解可能會相當耗時。 ## 補充 1. 決定一個整數是否為質數並不是一個NPC問題，而是P ->AKS質數測試