Introduction to Probability

Multivariable Calculus

Algorithms: Part II

Algorithms: Part I

Introduction to Software Design and Architecture

Calculus Two: Sequences and Series

LAFF Linear Algebra

Stanford Machine Learning

Calculus One

Computational Thinking

Effective Thinking Through Mathematics

CS50 Introduction to Computer Science

Others

Union-Find & Analysis of Algorithms

  • This case shows that, how to improve algorithm step by step.

Dynamic Connectivity

  • Given a set of N objects.

    • Union command: connect two objects.
    • Find/connected query: is there a path connecting the two objects?
  • We assume “is connected to” is an equivalence relation:

    • Reflexive: p is connected to p.
    • Symmetric: if p is connected to q, then q is connected to p.
    • Transitive: if p is connected to q and q is connected to r, then p is connected to r.

First Solution: Connected components

  • Maximal set of objects that are mutually connected.

Second Solution: Quick Find

  • To merge components containing p and q, change all entries
    whose id equals id[p] to id[q].

Third Solution: Quick Union

Forth Solution: Improved Quick Union

Final Solution: Weighted quick-union with path compression

  • quick-union:

  • weighted: Keep track of size of each tree (number of objects). Balance by linking root of smaller tree to root of larger tree.

    • Keep the depth of any node x is at most lg N.
  • path compression: Make every other node in path point to its grandparent.

  • Code:

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    package week1;

    import common.StdIn;

    import java.io.FileNotFoundException;
    import java.util.Scanner;

    public class UnionFind {

    private int count;
    private int[] parent;
    private int[] sz; // record the weight

    UnionFind(int n) {
    count = n;
    parent = new int[n];
    sz = new int[n];
    for(int i=0; i<n; i++) {
    parent[i] = i;
    sz[i] = 1;
    }
    }

    public int root(int id) {
    while (parent[id] != id) {
    parent[id] = parent[parent[id]]; // improve
    id = parent[id];
    }
    return id;
    }

    public boolean connected(int p, int q) {
    return root(p) == root(q);
    }

    // quick union
    public void union(int p, int q) {
    int rootP = root(p);
    int rootQ = root(q);
    if(sz[rootP] <= sz[rootQ]) {
    parent[rootP] = rootQ;
    sz[rootQ] += sz[rootP];
    } else {
    parent[rootQ] = rootP;
    sz[rootP] += sz[rootQ];
    }
    count --;
    }

    public int count() {
    return count;
    }

    public static void main(String[] args) {
    Scanner sc = null;
    try {
    sc = new Scanner(StdIn.getDataFile("mediumUF.txt"));
    } catch (FileNotFoundException e) {
    e.printStackTrace();
    }
    int n = sc.nextInt();
    UnionFind uf = new UnionFind(n);
    while (sc.hasNext()) {
    int p = sc.nextInt();
    int q = sc.nextInt();
    if (uf.connected(p, q)) continue;
    uf.union(p, q);
    System.out.println(p + " " + q);
    }
    System.out.println(uf.count() + " components");
    }
    }

Analysis of Algorithms

Common Order-of-growth Classifications

  • 1,logN,NlogN,N2,N3, and 2N1, \log{N}, N \log{N}, N^2, N^3, \text{ and } 2^N
    • order of growth discards leading coefficient
  • * $\text{time} = \lg{T(N)}$ * $\text{size} = \lg{N}$

Theory of Algorithms

Why Big-Oh Notation

  • Formal Definition: T(n)=O(f(n))T(n) = O(f(n)) if and only if there exist constants c,n0>0c,n_0 > 0 such that T(n)cf(n)T(n) \le c \cdot f(n) for all nn0n \ge n_0

    • T(n)T(n) is the function of the running time of an algorithm.
    • Warning c,n0c, n_0 cannot depend on n.
  • [NOTE] It kinds of says, we use nkn^k, but not nk1n^{k-1}

    • Because O(nk1)=cnk1O(n^{k-1}) = c \cdot n^{k-1} will always less then nkn^k (c is a constant, but n is not).
    • And we need that, T(n) is bounded above by a constant multiple of f(n).
  • Example

Assignment (Percolation)

Words

  • asymptotic [,æsimp’tɔtik,-kəl] adj. 渐近的;渐近线的
  • ubiquitous [ju:'bikwitəs] adj. 普遍存在的;无所不在的