112考資工研究所時寫的筆記，有錯歡迎留言指正
內文有引用他人筆記/教材/文章的地方
若有侵權十分抱歉，告知後將立刻撤除

Analysis algorithm
Divide and conquer
Dynamic programming
Graph
NP complete & approximation algo
- NPC
- approx algo

資源

註:

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Analysis algorithm

Time complexity definition
- $O (g (n)) = {f (n) : \exists c, n_{0} > 0 s u c h t h a t 0 \leq f (n) \leq c g (n), \forall n \geq n_{0}}$
- $Ω (g (n)) = {f (n) : \exists c, n_{0} > 0 s u c h t h a t 0 \leq c g (n) \leq f (n), \forall n \geq n_{0}}$
- $Θ (g (n)) = {f (n) : \exists c_{1}, c_{2}, n_{0} > 0 s u c h t h a t 0 \leq c_{1} g (n) \leq f (n) \leq c_{2} g (n), \forall n \geq n_{0}}$
  - $f (n) = Θ (g (n)) ⟺ lim_{n \to \infty} \frac{f (n)}{g (n)} = L > 0$
- $o (g (n)) = {f (n) : \forall c > 0, \exists n_{0} > 0 s u c h t h a t 0 \leq f (n) < c g (n), \forall n \geq n_{0}}$
  - $f (n) = o (g (n)) ⟺ lim_{n \to \infty} \frac{f (n)}{g (n)} = 0$
- $ω (g (n)) = {f (n) : \forall c > 0, \exists n_{0} > 0 s u c h t h a t 0 \leq c g (n) < f (n), \forall n \geq n_{0}}$
  - $f (n) = ω (g (n)) ⟺ lim_{n \to \infty} \frac{f (n)}{g (n)} = \infty$
- Stirling's approximation
  - $n! = Θ (n^{n + \frac{1}{2}} e^{- n})$
證明f(n)是否為poly-bounded
- 法1: 找到常數k使得
  $f (n) = O (n^{k})$
- 法2:
  $\lg (f (n)) = O (\lg n)$ (上式兩邊同取lg, proof: p7)
asymptotic notation沒有三一律
- 課本p2
- $f (n) = O (g (n)) 與 f (n) = Ω (g (n))$ 都不成立是有可能的
ch1常考題型/心得
- grow rate 比大小 (ex. )
  - 極限比較(可能要羅必達)
  - 記得n!永遠在最後(如果沒有
    $n^{n}$ 的話)
  - 代大數(不建議，很可能錯)
- 求time complexity
  - Master theorem (p11例2)
  - 直接從定義推導，找出常數(
    $\exists c, n_{0}$ such that …) (p2例2)
  - 暴力展開 (p4例6)
  - Substitution method
    - 要先猜or用master theorem or用tree看出，在驗證 (p14例7)
  - 離散解法
    - ex.
      $T (n) = 2 T (\sqrt{n}) + \lg n$ 很常拿來嚇人(p34習42d)
  - 畫tree
    - $O (n \lg n)$ :
      - ex. T(n)=T(0.3n)+T(0.2n)+T(0.5n)+cn，裡面比例和=1 (p30習30)
    - $O (n)$ :
      - ex. T(n)=T(0.3n)+T(0.2n)+cn，裡面比例和<1 (p31習31)
- 看code求複雜度
  - 沒啥技巧，通常簡單 (p28習24)
- $\lg (n!) = Θ (n \lg n)$ (p4例4)
  - 看到
    $Θ$ 就知道要證
    $O$ 和
    $Ω$
- $(\lg n)!$ is not ploynomial bounded
  - 記吧, 參考stackoverflow
- 例7, 習6, 15, 16, 43, 45, 47, 51b

Divide and conquer

merge sort




























Merge_sort(A,p,q){
    if(p<q){
        m=(p+q)/2;
        Merge_sort(A,p,m);
        Merge_sort(A,m+1,q);
        Merge(A,p,m,q);
    }
}

Merge(A,p,m,q){
    int n1=m-p+1, n2=q-m;
    int L[n1], R[n2];
    copy A[p,m] to L[1,n1];
    copy A[m+1,q] to R[1,n2];
    L[n1+1]=R[n2+1]=inf;
    
    int i=j=1;
    for(int k=p;k<=q;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i++;
        }
        else{
            A[k]=R[j];
            j++;
        }
    }
}

Max subarray problem




1. A[1...n]分成左右陣列B=[1...n/2], C[(n/2)+1...n];
2. 遞迴算B,C的Max subarray B1,C1，令他們的元素和分別為lmax, rmax;
3. 計算包含A[n/2], B[(n/2)+1]兩個值的max subarray D，最大元素和cmax
4. return max{lmax,rmax,cmax};

第1,3行:
$Θ (n)$
第2行:
$2 T (n / 2)$
$T (n) = 2 T (n / 2) + Θ (n) = Θ (n \lg n)$
DP 解(p48)







Max_subarray_DP(A,n){
    max=A[1];
    r=max;
    for i:2~n
        r=Max(A[i],A[i]+r);
    max=Max(max,r)
}

Matrix multiplication

懶的背
$T (n) = 2 T (\frac{n}{2}) + Θ (n^{2})$

Selection problem

求第k小的數







Select(A,k){
    p=Median_of_median(A);
    求S1=A中所有小於p的數，S2=A中所有大於p的數，設p為第x小的數
    if (k=p) return p;
    else if(k<x) return 剩餘數列中第k小的數
    else if(k>x) return 剩餘數列中第k-|S1|小的數
}

$T (n) = O (n \lg n)$
- Median_of_median(A):
  $T (n) = T (\frac{n}{5}) + T (\frac{3 n}{4}) + O (n) = O (n)$

The closet pair problem

p53
大致如下
- 把pair依照y座標排列
- 畫線垂直x軸，把P中的點分成左右: L,R
- 求左右closet pair距離:dl, dr，最短距離d=min{dl,dr}
- 找跨越中線的closet pair, 找到某個點離中線距離<d，往後面看7個點是否在中線兩邊 (看課本講)
- return d
$T (n) = 2 T (n / 2) + Θ (n)$

Dynamic programming

兩種情況能用DP

Optimal substructure
- 一個問題的最佳解，是由子問題的最佳解構成
Overlapping subproblem
- A recursive algorithm revisits the same subproblem over and over again.

Rod cutting

Given a rod of length n inches and an array of prices that includes prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
給定一根長度為n的繩子和一個價格陣列，其中包括所有尺寸小於 n 的長度價格。
求切繩子最多能賣多少錢。



















int cutRod(int price[], int n)
{
   int val[n+1];
   val[0] = 0;
 
   for(int i = 1; i<=n; i++)
   {
       int max_val = INT_MIN;
       for(int j = 0; j < i; j++)
         max_val = max(
           max_val, 
           price[j] + val[i-j-1]
       );
       val[i] = max_val;
   }
 
   return val[n];
}

time complexity:

Θ (n^{2})

參考

geeksforgeeks

Fractional (Continuous) knapsack

1. 計算Vi/Wi
2. 從大到小排列
3. 依序取物直到負重達到W或物品被取光

time complexity:

O (n \log n)

–>sort

0-1 knapsack

兩種方法，一個用2D array做，一個用1D array做。

2D版:
可以還原拿到哪些物品，並知道最高價值。
時間複雜度
$O (n W)$ ，空間複雜度
$O (W)$ 。N是物品數量，W是背包重量限制。而W的數值會隨input size成指數成長關係，為NPC，(目前)不是ploynomial time solvable


















int knapsack(int Weight, int wt[], int val[], int n)
{
    int dp[n + 1][Weight + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++)     // 窮舉每種物品
        for (int w = 0; w <= Weight; w++)// 窮舉每種重量
            if (wt[i] <= w) // w:目前背包還能裝多重的東西
                // 耐重能力足夠，可以放或不放。
                dp[i+1][w] = max(
                    dp[i][w],
                    dp[i][w - wt[i]] + val[i]
                );
            else
                dp[i+1][w] = dp[i][w];// 耐重能力不足，故只能不放。

    return dp[n][Weight];
}

1D版
只能知道最高價值
Time Complexity:
$O (n W)$ . As redundant calculations of states are avoided.
Auxiliary Space: O(W) As we are using 1-D array instead of 2-D array.


















int knapSack(int Weight, int wt[], int val[], int n)
{
    // making and initializing dp array
    int dp[Weight + 1];
    memset(dp, 0, sizeof(dp));
 
    for (int i = 0; i < n; i++) {
        for (int w = Weight; w >= 0; w--) {
 
            if (wt[i] <= w) 
                // finding the maximum value
                dp[w] = max(
                    dp[w],
                    dp[w - wt[i]] + val[i]);
        }
    }
    return dp[Weight]; // returning the maximum value of knapsack
}

參考:

表格怎麼畫
PS: 這個表格基本上跟code原理一樣，看著題目對照code寫一次就會了!
~~多畫幾次就會發現憑感覺畫會比快~~
表格怎麼畫2
Code source(1-D array)
Code source(2-D array)
陳縕農講knapsack變化題

Matrix Chain Multiplication

看印度人講解

遞迴式
- $s [i, j] = min_{i \leq k < j} {s [i, k] + s [k + 1, j] + p_{i - 1} p_{k} p_{j}} f o r i < j, o t h e r w i s e 0$
畫表格(以考古14題為例，p97)
- 有n個矩陣，需要兩個表格，分別為
  $n \times n$ 和
  $(n - 1) \times (n - 1)$
  - 記得先處理兩個的table的對角線，也注意index有無標錯
  - (2,1), (3,2), (4,3), (5,4)可以直接填入A1A2A3, A2A3A4…相乘的次數
  - 然後就照公式推

bottom-up






















int MatrixChainOrder(int p[], int n)
{
    int m[n][n], s[n][n]; // s[n][n] is used to record 括號位置
    int i, j, k, L, q;
    for (i = 1; i < n; i++)
        m[i][i] = 0;
    for (L = 2; L < n; L++)
        for (i = 1; i < n - L + 1; i++){
            j = i + L - 1;
            m[i][j] = INT_MAX;
            for (k = i; k <= j - 1; k++){
                q = m[i][k] + m[k + 1][j]
                    + p[i - 1] * p[k] * p[j];
                if (q < m[i][j]){
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
 
    return m[1][n - 1];
}

memoization





















int dp[100][100];
int MatrixChainOrder(int* p, int n)
{
    int i = 1, j = n - 1;
    return matrixChain(p, i, j);
}
int matrixChain(int* p, int i, int j)
{
    if (i == j)
        return 0;
    if (dp[i][j] != -1)
        return dp[i][j];
    dp[i][j] = INT_MAX;
    for (int k = i; k < j; k++)
    {
        dp[i][j] = min(
            dp[i][j], 
            matrixChain(p,i,k) + matrixChain(p,k+1,j)+p[i-1]*p[k]*p[j]);
    }
    return dp[i][j];
}

參考

geeksforgeeks

Optimal binary search tree (OBST)

畫表格:

i	0	1	2	3	4
pi	X	5	2	4	3
qi	3	2	3	4	2

ps: if no dummy node, all qi become 0

W[i][j] = W[i][j-1]+p[j]+q[j] –>先畫出W表
S[i][j] = min(i≤r≤j) { s[i][r-1]+s[r+1][j]+w[i][j] } –>依照剛剛的W表和題目給的pi, qi表畫出來
邊畫邊紀錄r表(哪個r讓S[i][j]有min)
看r表的形狀畫出Optimal search tree

資結用的算法和algo教的不同，資結版把C_ii全設為0(s table的對角線)，而非algo版的對應q_i的值。也就是資結版不算入failure node level的cost，考試時需要自行註明

參考:

表格怎麼畫(無dummy node)
有dummy node的題目跟著講義答案做一次就會了(林立宇p.76兩題都要寫!!!)
許建平ch15-3投影片

Longest Common sequence (LCS)

Time complexity:

O (n^{2})



















LCS(x,y){
    m=x.length;
    n=y.length;
    
    int s[m+1][n+1]; // 算長度用的
    int r[m+1][n+1]; // 畫箭頭用的
    
    for(int j=0;j<n;j++) // initialize
        s[0,j]=0;
    
    for(int i=1;i<=m;i++)
        s[i,0] = 0;
        for(int j=1;i<=n;j)
            if(xi==yi)
                s[i][j], r[i,j] = s[i-1][j-1], '左上箭頭';
            else
                s[i][j] ,r[i][j]
                    = max((s[i-1][j], '上箭頭'), (s[i][j-1], '左箭頭'));
}

Longest increasing sequence (LIS)

考試應該寫出

O (n^{2})

就夠了，不然LIS的

O (n \log n)

版本有點複雜




LIS(A){
    B = A.sort(); // O(nlogn)
    return LCS_length(A,B); // O(n^2)
}

Longest common substring





















LCS(x,y){
    m=x.length;
    n=y.length;
    
    int s[m+1][n+1];
    int length = 0;
    
    for(int j=0;j<n;j++) // initialize
        s[0,j]=0;
    
    for(int i=1;i<=m;i++)
        s[i,0] = 0;
        for(int j=1;i<=n;j
            if(xi==yi)
                s[i][j] = s[i-1][j-1]+1;
                length = max(length, s[i][j]);
            else
                s[i][j] = 0;
            
    return length;
}

Longest palindrome subsequence

目前只有台大105考過先放掉

Minimum edit distance

看影片畫表格，這個滿簡單的





































int editDistDP(string str1, string str2, int m, int n)
{
    // Create a table to store results of subproblems
    int dp[m + 1][n + 1];
 
    // Fill d[][] in bottom up manner
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            // If first string is empty, only option is to
            // insert all characters of second string
            if (i == 0)
                dp[i][j] = j; // Min. operations = j
 
            // If second string is empty, only option is to
            // remove all characters of second string
            else if (j == 0)
                dp[i][j] = i; // Min. operations = i
 
            // If last characters are same, ignore last char
            // and recur for remaining string
            else if (str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
 
            // If the last character is different, consider
            // all possibilities and find the minimum
            else
                dp[i][j]
                    = 1 + min(
                            dp[i][j - 1], // Insert
                            dp[i - 1][j], // Remove
                            dp[i - 1][j - 1]
                            ); // Replace
        }
    }
 
    return dp[m][n];
}

參考
geeksforgeeks

The KMP algorithm

目前看到的都是畫表格題型，code要不要背再斟酌
prefix func畫表格: 肉眼比對一下前綴(prefix)後綴(postfix)長度就好了
prefix funtion全部-1後就是failure function

下面為failure function













void fail(string B, int *pi)
{
    int len = B.length();
    pi[0] = -1;
    for( int i = 1, cur_pos = -1; i<len; ++i)
    {
        while(cur_pos >= 0 && B[i] != B[cur_pos+1])
                cur_pos = pi[cur_pos];
        if(B[i] == B[cur_pos+1])  ++cur_pos;
        pi[i] = cur_pos;
    }

}// prefix function只需要把p[i]中每個值+1即可

參考
🌟成大資工wiki: KMP
🌟畫表格
 影片示範
 初學者學 KMP 演算法

change-making (coin-changing)















coin_changing(){    
 // int n = 99; // 99: return -1,不能換成零錢!
    int n= 100; // 100: 要把100全換成零錢
    int dp[n+1]; 
    int coins[] = {6,4,10,50};
        dp[0] = 0;
        for(int i = 1; i <= n; ++i) {
            dp[i] = INT_MAX;
            for(int coin : coins)
                if(i >= coin && dp[i-coin] != -1)
                    dp[i] = min(dp[i], 1 + dp[i-coin]); 
            if(dp[i] == INT_MAX) dp[i] = -1;
        }
        cout<< dp[n];
}

Huffman

Time complexity:

O (n \log n)










HUFFMAN( C )
n = |C|
Q = C /* initialize the min-priority queue with the character in C */
for i: 1 to n – 1
    allocate a new node z
    z.left = x = EXTRACT-MIN(Q)
    z.right = y = EXTRACT-MIN(Q) // 抓出最小的兩個node
    z.freq = x.freq + y.freq // 合併成一個
    INSERT(Q, z)  // 放回Queue
return EXTRACT-MIN(Q) // return the root of the tree

subset sum

可以被reduce成01 knapsack，詳細怎麼做還要再查































#include <stdio.h>
  
bool isSubsetSum(int set[], int n, int sum)
{
    // The value of subset[i][j] will be true if
    // there is a subset of set[0..j-1] with sum
    // equal to i
    bool subset[n + 1][sum + 1];
  
    // If sum is 0, then answer is true
    for (int i = 0; i <= n; i++)
        subset[i][0] = true;
  
    // If sum is not 0 and set is empty,
    // then answer is false
    for (int i = 1; i <= sum; i++)
        subset[0][i] = false;
  
    // Fill the subset table in bottom up manner
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j < set[i - 1])
                subset[i][j] = subset[i - 1][j];
            if (j >= set[i - 1])
                subset[i][j] = subset[i - 1][j]
                               || subset[i - 1][j - set[i - 1]];
        }
    }
  
    return subset[n][sum];
}

參考
geeksforgeeks

Graph

圖的名詞補充:
- light edge：考慮所有cross edge中，「weight最小」的edge稱為light edge(可以不只一條)
- Cut: (S,V−S)是一種將Graph(G=(V,E))的V(vertex set)分成兩部分的partition(分割)
- Cross:若存在一條edge(X,Y)，其中X⊆S，Y⊆V−S，則稱這條edge「crosses」 Cut (S,V−S)
- Respect: Set A中沒有任何一條edge是Cut的crossing edge，則稱這個Cut「respect」 Set A。(因為尊敬，所以不切開。)
- Safe edge: edge對Set A來說是安全的(safe)，使得「該edge加入Set A後，Set A仍然滿足 A⊆E(MST)
- (109清大計科, 109台大資演)
- distance: 兩點間最短路徑的長度
- eccentricity: 從某點v到其他點的最長的distance (或指該條最長路徑)
- diameter: 某圖中最大的eccentricity
- radius: 某圖中最小的eccentricity
- center: 形成radius的vertex (只有1 or 2個)

Elementary Graph Algorithms

BFS

Time complexity:
- $O (V + E)$ (下面的algo，用adjacency list存G)
- $O (V^{2})$ (用adjacency matrix存G)




























// π: parent
// d: s到u的距離
// Adj: 相鄰的vertex
// 
// color
// white: undiscovered,
// gray: discovered但存在undiscovered的neighbors
// black: 自己和neighbors皆為discovered
BFS(G,s){
    for each vertex u ∈ G.V - {s}
        u.color = WHITE
        u.d = ∞
        u.π = NIL
    s.color = GRAY
    s.d = 0
    s.π = NIL
    Q = ∅;
    ENQUEUE(Q,s)
    while Q ≠ ∅ ;
        u = DEQUEUE(Q)
        for each v ∈ G.Adj[u]
            if v.color == WHITE
                v.color = GRAY
                v.d = u.d+1
                v.π = u
                ENQUEUE(Q,v)
        u.color = BLACK
}

上面是algo課本CLRS的，下面是陳宜欣slides的版本


















void Graph::BFS(int v){
    visited = new bool[n]; // this is a data member of Graph
    fill(visited, visited+n, false);
    Queue<int> q; // declare and init a queue
    q.Push(v);
    visited[v]=true;
    while(!q.IsEmpty()){
        v = q.Front(); q.Pop();
        output(v);
        for(each vertex w adjacent to v){
            if(!visited[w]){
                q.Push(w);
                visited[w]=true;
            }
        }
    }
    delete [] visited;
}

DFS

Time complexity
- $O (V + E)$ (下面的algo，用adjacency list存G)
- $O (V^{2})$ (用adjacency matrix存G)

























// d: discover time 
// f: finish time
// t: time
DFS(G){
    for each vertex u in G.V
        u.color = WHITE
        u.π = NIL
    t = 0;
    for each vertex u in G.V
        if u.color == WHITE
            DFS-VISIT(G,u)
}


DFS-VISIT(G,u){
    t++
    u.d = t
    u.color = GRAY
    for v in G.Adj[u]
        v.π = u
        DFS-VISIT(G,v)
    u.color = BLACK
    t++
    u.f = t
}

上面是algo課本CLRS的，下面是陳宜欣slides的版本

Recursive DFS(簡易)







void Graph::DFS(const int v){
    // visit all previously unvisited vertices that are adjacent to v
    output(v);
    visited[v]=true;
    for(each vertex w adjacent to v)
        if(!visited[w]) DFS(w);
}

Non-Recursive DFS(簡易)















void Graph::DFS(int v){
    visited = new bool[n]; // this is a data member of Graph
    fill(visited, visited+n, false);
    Stack<int> s; // declare and init a stack
    s.Push(v);
    while(!s.IsEmpty()){
        v = s.Top(); s.Pop();
        if(!visited[v]){
            output(v);
            visited[v]=true;
        for(each vertex w adjacent to v)
            if(!visited[w]) s.Push(w);
        }
    }
}

DFS後，把edge分成4種:
1. Tree: Edges in the DFS forest
2. Back: From descendant to ancestor when explored (include self loop)
3. Forward: From ancestor to descendant when explored (exclude tree edge)
4. Cross: Others (no ancestor-descendant relation)

topological sort

Time complexity
- $O (V + E)$ (with stack)
topological sort存在 <–> G是acyclic(無環)

Strongly Connected Component (SCC)

Time complexity: 同DFS
Finding_all_SCC又稱作Kosaraju's algorithm






Finding_all_SCC{
    DFS(G); // 算出所有v的v.f
    Construct(G^T); // 建G^T，把所有G的edge都反向:(u,v)-->(v,u)
    DFS(G^T); // 依照v.f的順序由大到小對G^T做DFS
    return tree_find_in_line_4; //(G^T)找到的每顆tree即為SCC
}

Minimum spanning trees (MST)

MST上的path必為minimax path (p172. 30題)
shortest path tree不是MST !!!
- 用single source shortest path 找(Dijkstra, Bellman-Ford)

Kruskal

Time complexity:
- $O (E \lg V)$ (sorted, adjacency list)
- $O (E \lg E)$ (Unsorted, adjacency list)
- $O (V^{2})$ (adjacency matrix with array)
不會形成loop的前提下，每次都挑最小的邊，直到所有v被包含








Kruskal’s_MST(G){
    MST = set();
    sort(E); // increasing order by weight
    for e in E:
        if add e won't form a cycle in MST:
            MST = MST U {e};
    return MST;
}

Prim's

Time complexity:
- $O (E \lg V)$ (binary heap)
- $O (V \lg V + E)$ (Fibonacci heap)
- $O (V^{2})$ (adjacency matrix with array)
隨便選個root，不會形成loop的前提下，把他到鄰居最小的edge選出來，直到所有v被包含
CLRS版













MST-PRIM(G w, r){    
    for each in G.V
        u.key = 1;
        u.π = NIL;
    r.key = 0;
    Q = G.V; // Q是priority Queue, 可以用Heap實作
    while(!Q.empty())
        u = EXTRACT-MIN(Q);
        for each v in G.Adj[u]
            if v in Q and w(u,v) < v.key
                v.π = u
                v.key = w(u,v);
}

遞迴版





Prim-MST(G, u)
    Set u as the source vertex
    Find the cheapest (non-self-loop) edge from u, say, (u,v)
        Merge v into u to obtain G*
    Prim-MST(G*, u)

補充: 還有一種MST algo 叫Sollin's algorithm，只有在陳宜欣的slides裡面有，真的很閒再去學

Single source shortest paths

Dijkstra

Time complexity:
- $O ((V + E) \times \lg V)$ (binary heap)
- $O (V \lg V + E)$ (Fibonacci heap)
- $O (V^{2})$ (array)
不能有負邊!!!
表格: p.131
下面的code很pseudo考試應該要自己再轉換
















Dijkstra(G, s){
    For each vertex v:
        Mark v as unvisited;
        set d(v) = ∞ ;
    Set d(s) = 0 ;
    while (there is unvisited vertex) {
        v = unvisited vertex with smallest d(v);
        Visit v, and Relax all its outgoing edges;
    }
    Return d;
}

Relax (u, v, w){
    If d(v) > d(u) + w(u, v)
        d(v) = d(u) + w(u, v);
}

Bellman-Ford

Time complexity:
- $O (V E)$ (adjacency list)
可以有負邊，不能有負環(所有最短路徑演算法都不能有負環，會無解)
第5行不一定要做到V-1次，如果某次relax完，發現沒有被更新，就可以停了
因為做到V-1也不會改變!
但如果多做1次，也就是V次，還被更新，表示存在負環
表格: p.135，
- 注意每一個k代表要relax每個source以外的點一次，順序沒差
- 可以把到每個vertex的最短距離寫在圖的vertex上
- relax過程中需要一直改圖上和表格中的內容
- 做一次應該就知道了，記得熟悉演算法原理
負環: sum of edge weight in a cycle is negative












Bellman-Ford(G, s){ // runs in O(VE) time
    For each v: // initialize
        set d(v) = INF;
        Set d(s) = 0;
    for(k = 1 to |V|-1)
        Relax all edges in G in any order;
    /* check if s reaches a neg-weight cycle */
    for each edge (u,v)
        if (d(v) > d(u) + weight(u,v))
            return “Negative cycle!”;
    return d;
}

DAG shortest path

Time complexity:
- $O (V + E)$
DAG –- Directed Acyclic Graph















DAG-Shortest-Path(G, s, w){
    Topological Sort(G) to get <v1,v2,...vn>;
    Initialize(G,s);
    for i=1 to n:
        for each v in adj[vi]:
            Relax(vi,v,w);
}
Initialize(G,s){
    For each v in G:
        set d(v) = INF;
}
Relax (u, v, w){
    If d(v) > d(u) + w(u, v)
        d(v) = d(u) + w(u, v);
}

DAG longest path

把上面shortest path的程式改成:

inf -> -inf
$>$ ->
$<$
(所有edge weight乘-1): 應該不用

All pairs shortest paths

Floyd-Warshall

Time complexity:
- $O (V^{3})$
W是G的adjacency matrix, 允許負邊，沒負環
檢查負環是否存在: 做完看矩陣對角線有沒有負數
Transitive closure: 檢查兩點間有無path
▲
第7行前都在initialize，相鄰的就寫1，其他寫0

Johnson

Time complexity:
- $O (V E + V^{2} \log V)$ (Fibonacci Heap)
- $O (V E \log V)$ (Binary heap)
- E很小時，比Floyd-Warshall快
改寫negative weight成positive
- 建一個新的vertex: s
- 把他和每個圖中的點相接，edge皆設0
- 把每個vertex加上weight=δ(s,v) –>s到v最短距離
- 改寫edge weight: ŵ(u,v)=w(u,v)+δ(s,u)-δ(s,v)
Pseudo code
上面翻譯:
1. 加入點s，從他連接每個vertex的w都設0
2. 用Bellman-Ford檢查是否存在負環，如果有就GG
3. 沒負環，用bellman-Ford把每個vertex的weight h(v)設s到v最短距離(bellman-ford)
4. 改寫wight:
  $\hat{w} (u, v) = w (u, v) + δ (s, u) - δ (s, v)$
5. 對每個點跑Dijkstra，計算到彼此的最短距離
  $\hat{δ} (u, v)$
6. 剛剛的距離是改寫過的，真正最短距離要改回來:
  $d_{u v} = \hat{δ} (u, v) + h (v) - h (u)$

Maximum flow

minimum cut: 值同Maximum flow
- 從source流到terminal的path上，第一個滿的edge，就是bottleneck(就是他害你不能流更多水)，該edge就在Minimum cut中 (見p223, 103題)
Residual network: 有逆向箭頭的那個圖 (往回流)
augmenting path: residual network中，能從s流到t的path。
- 如果找不到augmenting path，代表找到maximum flow了

Ford-Fulkerson

Time complexity:
- $O (E \times | f^{*} |)$
- $f^{*}$ 是maximum flow









Ford-Fulkerson(G,s,t){
    Initialize flow f to 0;
    while(exist augmenting path P in G){
        Augment flow f along P;
        update G;
    }
    return f;
}

Edmonds-Karp

Time complexity:
- $O (V E^{2})$
和Ford-Fulkerson唯一區別: 找augmenting path用BFS(Ford-Fulkerson沒限制)

Maximum Bipartite matching

Time complexity:
- $O (V E)$
- 因為用Ford-Fulkerson找=
  $O (E \times | f^{*} |)$
- 其中
  $f^{*}$ 是maximum flow，不會超過vertex數量
目標: 找出最多pair
作法:
- 左邊加上source s連接L的每個vertex v
- 又邊加上terminate t連接R的每個vertex u
- 每條edge的capacity c(u,v)=1
- 找maximum flow

NP complete & approximation algo

NPC

經典NPC問題
- 3-CNF-SAT
- Clique
- vertex-cover
- k-coloring (determine whether a graph can be colored with k colors)
  - k=2, BFS can done, k>2, NPC
- Hamiltonian Cycle
  - cycle經過每個點洽一次
- Hamiltonian path
  - path經過每個點洽一次
- Traveling salesman problem
  - complete graph中是否cost至少為k的hamiltonian cycle
- Longest Path
  - graph中是否存在長度至少為k的path (不一定經過每個點!)
- 01 knapsack
- Min-Flow/Max-cut (不是max-flow/min cut !)
常被誤會的P問題
- 2-CNF-SAT
- Euler circuit
- Euler trail
- Shortest path (SSSP, APSP)
通常證明套路 (ex. 證明TSP是NPC)
1. TSP
  $\in$ NP
  - 可以在poly-time驗證某個case是否為TSP
2. HC
  $\leq_{p}$ TSP
  - 看下面我懶得打

approx algo

vertex-cover









approx_vertex_cover(G){
    C={};
    E' = edge set of G;
    while (!E'.empty()){
        Let (u,v) be arbitrary edge in E';
           C = C + (u,v);
           remove all edge in E' with end point u or v;
    }
}

證明他是2-approximation algo:
- In line 5，every edge can only covered by its endpoint
- Therefore, in each iteration, one of the selected vertex must be in the optimal vertex cover

Euclidean traveling salesman problem (ETSP)

我們無法在一般的TSP中找到approximation algorithm
以下是在歐幾里得平面上的TSP問題的近似演算法







Approx_ETSP(G){
    求G的MST;
    從r開始preorder traverse T
        走到新結點，加入H;
    最後把r加入H;
    return H;
}

證明他是2-approximation algo:

Maximum cut

minimum cut (maximum flow) 的相反問題
證明他是2-approximation algo:
When a vertex v is fixed, we will add some edges into the cut, and discard some edges (u, v) if u is placed in the same set as v
But when each vertex is fixed :
#edges added
$\geq$ #edges discarded
$⟹$ total #edges added
$\geq$ m/2
Time Complexity Table

class	algorithm	time complexity
Basic
	BFS	$O (V + E) l i s t, O (V^{2}) m a t$
	DFS	$O (V + E) l i s t, O (V^{2}) m a t$
	TP sort	$O (V + E)$
	SCC	$O (V + E)$
MST
	Kruskal	$O (E \lg V) s o r t e d l i s t$
		$O (E \lg E) u n s o r t e d l i s t$
		$O (V^{2}) m a t$
	Prim	$O (E \lg V) b h$
		$O (V \lg V + E) F h$
		$O (V^{2}) m a t$
SSSP
	Dijkstra	$O ((V + E) \lg V) b h$
		$O (V \lg V + E) F h + l i s t$
		$O (V^{2}) m a t$
	Bellman-Ford	$O (V E) l i s t$
	DAG-SP(LP)	$O (V + E)$
APSP
	Floyd-Warshall	$O (V^{3})$
	Johnson	$O (V^{2} \lg V + V E)$ Fh
		$O (V E \lg V)$ bh
MaxFlow
	Ford-Fulkerson	$O (f^{*} \times E)$
	Edmonds-karp	$O (V E^{2})$

上表用詞解釋
- MST: minimum spanning tree
- SSSP: single source shortest path
- APSP: all source shortest path
- SCC: strongly connected component
- mat: matrix
- fh: fibonacci heap
- bh: binary heap