Union-Find & Analysis of Algorithms

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

1. 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.

1.1. First Solution: Connected components

  • Maximal set of objects that are mutually connected.

1.2. Second Solution: Quick Find

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

1.3. Third Solution: Quick Union

1.4. Forth Solution: Improved Quick Union

1.5. 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:

      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");
        }
      }
    

2. Analysis of Algorithms

2.1. 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
    • time=lgT(N)\text{time} = \lg{T(N)}
    • size=lgN\text{size} = \lg{N}

2.2. Theory of Algorithms

2.3. 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

3. Assignment (Percolation)

4. Words

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

results matching ""

    No results matching ""