Algorithm Design 1

发表于 更新于 分类于 ， 阅读次数： 本文字数： 675 阅读时长 ≈ 2 分钟
[2023 秋] 算法设计 第一课课堂笔记 / [2023 Fall] Algorithm Design Lecture 1 Notes

Chapter 0 Logistics

Content : discrete(combinatorial) algorithm , Theoretical

  • [minority] Complexity , NP-Completeness
  • Basic Graph Algorithm , DFS / BFS
  • Greedy
  • Dynamic Programming
  • Divide and Conquer
  • NP-completeness Theory
  • Approximation Algorithm
  • Randomized Algorithm (Probability Analysis)
    • Computational Geometry
    • Streaming Algorithm (online)

Textbook : [Kleinberg&Tardos] Algorithm Design

Reference Book : [CLRS] Intro to Algorithm

Chapter 1

1.1 Stable matching

  1. Def

    • Input : \(boys=\{B_1,\cdots,B_n\} , girls=\{G_1,\cdots,G_n\}\)

      Preference List : \(BP_i\) : a permutation of \(girls\) , \(GP_i\) : a permutation of \(boys\)

    • output : a stable matching

    • stable matching : no unstable pairs

    • unstable pair : \((B_i,G_j)\) s.t. \(M(B_i)\) after \(G_j\) in \(BP_i\) and \(M(G_j)\) after \(B_i\) in \(GP_j\)

  2. Efficient Algorithm : Gale & Shapley Algorithm ( propose-reject )

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    while( exists sb. single ){
        A <- an arbitrary single boy
        X <- first girl A has not proposed yet
        if ( X is single )
            A-X engage
        else
            if ( A is better than M(X) )
                A-X engage
            else
                X reject A
    }

  3. Analysis

    1. Proof of Termination

      1. For girl : once engaged , engaged forever
      2. For one boy : If used all preference list : then all girls must be engaged

    2. Proof of Correctness

      Prove by Contradiction

      \((B_i,G_j)\) : an unstable pair

      \(B_i\) preference list : \(\cdots G_j \cdots M(B_i)\)

      \(G_j\) preference list : \(\cdots B_i \cdots Z=M(G_j)\)

      \(\therefore\) \(G_j\) rejected \(B_i\) , but \(G_j\) should not reject \(B_i\) compared with \(Z\)

    3. Running Time : \(\mathcal O(n^2)\) ( All boys used up their preference list)

  4. Random ver.

    1. def : \(BP_i\) , \(GP_i\) are all random permutations (uniformly distributed)

    2. How to get a uniformly distributed random permutation ?

      draw-likely process

    3. THM : \(\mathbb E[T]\le n\cdot H_n\) (\(\mathbb E[T]=\mathcal O(n\log n)\))

    4. Proof

      1. key observation :

        G-S' : each time a boy propose to a random girl not proposed yet

        This is equivalent as generate a uniformly distributed random permutation

        G-S'' : each time a boy propose to a random girl (can be proposed yet)

        $$ \(T(G-S)=T(G-S')\le T(G-S'')\)

      2. Coupon Collector Problem ( Bins-Balls )

        \(n\) bins , each time throw a ball to a random bin .

        Q : \(\mathbb E[\text{balls}]\) s.t. every bin is nonempty .

        A : \(\mathbb E[\text{balls}]=n\cdot H_n\)

        Construct Sequence \(a_i\in \{0,1\}\) , \(a_i=1\Leftrightarrow\) a ball falls in an empty bin

        Exactly \(n\) number of \(1\)s . -> \(n\) segments like \(0\cdots 01\) \[ \begin{aligned} \mathbb E[T]&=\mathbb E\left[\sum_{i=1}^n \text{len of i-th segment}\right]\\ &=\sum_{i=1}^n\mathbb E\left[ \text{len of i-th segment}\right]\\ &=\sum_{i=1}^n \frac{1}{\Pr\{\text{in i-th seg , choosed empty bin}\}}\\ &=\sum_{i=1}^n \frac{n}{n-i+1}\\ &=n\cdot H_n \end{aligned} \]

      3. Consider boy -> ball , girl -> bin

        G-S'' -> Bins-Balls Problem

        • Concentration inequality for Coupon Collection Running Time

          Same as Chernoff Bound

1.2 BFS & DFS

  1. BFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    // bfs
    q.clear();
    for(u in Vertices){
        dep[u]=inf;
        prev[u]=NULL;
        col[u]=white;
    }

    dep[s]=0;
    prev[s]=NULL;
    col[s]=grey;
    q.push(s);

    while(!q.empty()){
        u=q.front();q.pop();
        for(v in Neighbour(u) ){
            if(col[v]==white){
                dep[v]=dep[u]+1;
                prev[v]=u;
                col[v]=grey;
                q.push(v);
            }
        }
        col[v]=black;
    }

    BFS Tree Property : no edges with depth difference \(\ge 2\) .

  2. DFS

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function dfs(u){
        ++time;
        discover[u]=time;
        col[u]=grey;
        for(v in Neighbour(u) ){
            if(col[v]==white){
                dfs(v)
            }
        }
        col[u]=black;
        ++time;
        finish[u]=time;
    }

    DFS Tree Properties

    Time stamp intervals

    1. non-crossing : only non-intersect / totally include
    2. Tree Structure \(\Leftrightarrow\) Time stamp intervals Structure

  3. Connectivity

    1. undirected graph : connected component

    2. directed graph : strongly connected component (SCC)

      every vertex can reach other vertex

    3. directed acyclic graph (DAG)

      i.e. no directed cycle

      i.e. no SCC has \(\ge 2\) vertices

      • DAG has a topological order

    4. A useful view of directed graph : a DAG of SCC

      a.k.a. 缩点

    5. DAG has a topological order

      get topological order : use bfs/dfs starting from \(InDeg=0\)