Notes from https://www.coursera.org/learn/algorithms-part1/

Union-Find

• Apply the union-find data type to solve problems in science, engineering, and industry.
• Define the union-find (or disjoint sets) data type.
• Compare the performance of different algorithms for the union-find data type.
• Design different algorithms (quick find, quick union, weighted quick union, path compression) for the union-find data type.
• Develop Java implementations of different algorithms for the union-find data type.
• Use the parent-link representation to represent tree data structures.

Quick Find

• an algorithm for solving the dynamic connectivity problem, called Quick-find.

• Data structure:

  • Integer array id[] of length N. With each entry equal to its index.
  • Interpretation: p and q are connected iff they have the same id.

• Find: Check if p and q have the same id.
• Union: To merge components containing p and q, change all entries whose id equals id[p] to id[q].

Java implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class QuickFindUF{
    private int[] id;
    public QuickFindUF(int N)
    {
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    public boolean connected(int p, int q)
    { return id[p] == id[q]; }
    public void union(int p, int q)
    {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++)
            if (id[i] == pid) id[i] = qid;
    }
}

• Quick-find defect:
  • Union too expensive (N array accesses).
  • Trees are flat, but too expensive to keep them flat.

Quick Union

• Quick Find is too slow for huge problems. Quick-union is an alternative.
• Data structure.
  • Integer array id[] of length N.
  • Interpretation: id[i] is parent of i.
  • Root of i is id[id[id[…id[i]…]]].(keep going until it doesn’t change)

• Find. Check if p and q have the same root.
• Union. To merge components containing p and q, set the id of p’s root to the id of q’s root.

Java implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class QuickUnionUF {
    private int[] id;
    public QuickUnionUF(int N) {
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }
    private int root(int i) {
        while (i != id[i]) i = id[i];
        return i;
    }
    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }
    public void union(int p, int q) {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

• Quick-union defect:
  • Trees can get tall.
  • Find too expensive (could be N array accesses).

Quick-Union Improvements

Improvement 1: weighting

• Weighted quick-union:
  • Modify quick-union to avoid tall trees.
  • Keep track of size of each tree (number of objects).
  • Balance by linking root of smaller tree to root of larger tree.

• Data structure: Same as quick-union, but maintain extra array sz[i] to count number of objects in the tree rooted at i.

• Find. Identical to quick-union return root(p) == root(q);

• Union. Modify quick-union to:

  • Link root of smaller tree to root of larger tree.
  • Update the sz[] array.

  1 2 3 4 5

  int i = root(p); int j = root(q); if (i == j) return; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; }

• Proposition. Depth of any node x is at most lg N.

Improvement 2: path compression

• Quick union with path compression. Just after computing the root of p, set the id of each examined node to point to that root.

• Two-pass implementation: add second loop to root() to set the id[] of each examined node to the root.
• Simpler one-pass variant: Make every other node in path point to its grandparent (thereby halving path length).

1
2
3
4
5
6
7

private int root(int i){
  while (i != id[i]){
    id[i] = id[id[i]];
    i = id[i];
  }
  return i;
}

• It’s amazing fact that was eventually proved by Friedman and Sachs, that there is no linear time algorithm for the union find problem. But weighted quick union with path compression in practice is close enough that it’s going to enable the solution of huge problems.

Union-find applications

• Percolation: A model for many physical systems:
  • N-by-N grid of sites.
  • Each site is open with probability p (or blocked with probability 1 – p).
  • System percolates iff top and bottom are connected by open sites.

• Monte Carlo simulation:

  • Initialize N-by-N whole grid to be blocked.
  • Declare random sites open until top connected to bottom.
  • Vacancy percentage estimates p*.

• Dynamic connectivity solution to estimate percolation threshold:

  • Create an object for each site and name them 0 to N 2 – 1.
  • Sites are in same component if connected by open sites.
  • Percolates iff any site on bottom row is connected to site on top row. (brute-force algorithm: N² calls to connected())

• UPDATE: Introduce 2 virtual sites (and connections to top and bottom). Percolates iff virtual top site is connected to virtual bottom site. (efficient algorithm: only 1 call to connected())

Q. How to model opening a new site?
A. Mark new site as open; connect it to all of its adjacent open sites. (up to 4 calls to union())

##QUIZ

1. Social network connectivity.

Given a social network containing n members and a log file containing m timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be mlogn or better and use extra space proportional to n.

Hint: union−find.

2. Union-find with specific canonical element.

Add a method 𝚏𝚒𝚗𝚍() to the union-find data type so that 𝚏𝚒𝚗𝚍(𝚒) returns the largest element in the connected component containing i. The operations, 𝚞𝚗𝚒𝚘𝚗(), 𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍(), and 𝚏𝚒𝚗𝚍() should all take logarithmic time or better.

For example, if one of the connected components is {1, 2, 6, 9}, then the 𝚏𝚒𝚗𝚍() method should return 9 for each of the four elements in the connected components.

Hint: maintain an extra array to the weighted quick-union data structure that stores for each root 𝚒 the large element in the connected component containing 𝚒.

3. Successor with delete.

Given a set of nn integers S = { 0, 1, … , n-1 } and a sequence of requests of the following form:

• Remove x from S
• Find the successor of x: the smallest y in S such that y ≥ x.

design a data type so that all operations (except construction) take logarithmic time or better in the worst case.

Hint: use the modification of the union−find data discussed in the previous question.

Stacks and Queues

Stacks

linked-list implementation

1
2
3
4
5

//inner class
private class Node{
  String item;
  Node next;
}

• Stack pop

1
2
3
4
5

public String pop(){
  String item = first.item;
  first = first.next;
  return item;
}

• Stack push

1
2
3
4
5
6

public void push(String item){
  Node oldfirst = first;
  first = new Node();
  first.item = item;
  first.next = oldfirst;
}

array implementation

• push(): add new item at s[N].

• pop(): remove item from s[N-1].

Queue

linked-list implementation

1
2
3
4
5

//inner class
private class Node{
  String item;
  Node next;
}

• enqueue

1
2
3
4
5
6
7
8

public void enqueue(String item){
  Node oldlast = last;
  last = new Node();
  last.item = item;
  last.next = null;
  if (isEmpty()) first = last;
  else oldlast.next = last;
}

• dequeue

1
2
3
4
5
6

public String dequeue(){
  String item = first.item;
  first = first.next;
  if (isEmpty()) last = null;
  return item;
}

resizing array implementation

• Use array q[] to store items in queue.
• enqueue(): add new item at q[tail].
• dequeue(): remove item from q[head].
• Update head and tail modulo the capacity.
• Add resizing array.

applications

• Stack applications
  • Parsing in a compiler.
  • Java virtual machine.
  • Undo in a word processor.
  • Back button in a Web browser.
  • PostScript language for printers.
  • Implementing function calls in a compiler.

Evaluate infix expressions

• Two-stack algorithm. [E. W. Dijkstra]
  • Value: push onto the value stack.
  • Operator: push onto the operator stack.
  • Left parenthesis: ignore.
  • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Evaluate{
    public static void main(String[] args){
        Stack<String> ops = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();
        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();
            if (s.equals("(")) ;
            else if (s.equals("+")) ops.push(s);
            else if (s.equals("*")) ops.push(s);
            else if (s.equals(")")){
                String op = ops.pop();
                if (op.equals("+")) vals.push(vals.pop() + vals.pop());
                else if (op.equals("*")) vals.push(vals.pop() * vals.pop());
            }
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}

Elementary Sorts

selection sort

• selection sort
  • In iteration i, find index min of smallest remaining entry.
  • Swap a[i] and a[min].

1
2
3
4
5
6

for (int i = 0; i < N; i++){
    int min = i;
    for (int j = i+1; j < N; j++)
        if (less(a[j], a[min])) min = j;
    exch(a, i, min);
}

根据位置 在数集合中找位置对应的数放入

• Running time insensitive to input: Quadratic time, even if input is sorted.
• Data movement is minimal: Linear number of exchanges.

insertion sort

• insertion sort: In iteration i, swap a[i] with each larger entry to its left.

1
2
3
4
5
6
7
8
9

public static void sort(Comparable[] a){
    int N = a.length;
    //Moving from right to left, exchange a[i] with each larger entry to its left.
    for (int i = 0; i < N; i++)
        for (int j = i; j > 0; j--)
            if (less(a[j], a[j-1]))
                exch(a, j, j-1);
            else break;
}

一个不断扩张的有序数列

• Best case. If the array is in ascending order, insertion sort makes N- 1 compares and 0 exchanges.
• Worst case. If the array is in descending order (and no duplicates), insertion sort makes ~ ½ N² compares and ~ ½ N² exchanges.

shell sort

• Shell sort: Move entries more than one position at a time by h-sorting the array.

finding the best increment sequence is a research problem that has confounded people for quite a long time.

1
2
3
4
5
6
7
8
9
10
11
12
13

public static void sort(Comparable[] a){
    int N = a.length;
    int h = 1;
    while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, ...
    while (h >= 1){ // h-sort the array.
        for (int i = h; i < N; i++){
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                exch(a, j, j-h);
        }

        h = h/3;
    }
}

跳着比较和调整，每次缩小间隔，直到完全有序

We have to do a few extra passes to do the higher sorts but the each element moves only a little bit on each path and that’s how Shellsort gains its efficiency.(subquadratic)

Shuffling

• suppose you have a deck of cards, one of the things that you might want to try to do is to simply rearrange those cards into random order, that’s called shuffling.
• Knuth shuffle
  • In iteration i, pick integer r between 0 and i uniformly at random.
  • Swap a[i] and a[r].

1
2
3
4
5
6
7

public static void shuffle(Object[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int r = StdRandom.uniform(i + 1);
        exch(a, i, r);
    }
}

it’s key that the uniform random number be between 0 and i - 1.

每拿到一张牌，随机插入已有的牌中。

Convex hull

• The convex hull of a set of N points is the smallest perimeter fence enclosing the points.

application: motion planning

Robot motion planning. Find shortest path in the plane from s to t that avoids a polygonal obstacle.

Shortest path is either straight line from s to t or it is one of two polygonal chains of convex hull.

application: farthest pair

Farthest pair problem. Given N points in the plane, find a pair of points with the largest Euclidean distance between them.

Farthest pair of points are extreme points on convex hull.

Graham scan

• Graham scan

  • Choose point p with smallest y-coordinate.(Define a total order, comparing by y-coordinate.)
  • Sort points by polar angle with p.(Define a total order for each point p.)
  • Consider points in order; discard unless it create a counterclockwise turn.

• Given three points a, b, and c, is a → b→ c a counterclockwise turn? equals to is c to the left of the ray a→b ?

• (b_x − a_x )(c_y − a_y ) − (b_y − a_y )(c_x − a_x ) (b - a) × (c - a)
  • If signed area > 0, then a→ b→ c is counterclockwise.
  • If signed area < 0, then a→ b→ c is clockwise.
  • If signed area = 0, then a→ b→ c are collinear.

1
2
3
4
5
6

public static int ccw(Point2D a, Point2D b, Point2D c){
    double area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
    if (area2 < 0) return -1; // clockwise
    else if (area2 > 0) return +1; // counter-clockwise
    else return 0; // collinear
}

Mergesort

Mergesort

• Basic plan.

  • Divide array into two halves.
  • Recursively sort each half.
  • Merge two halves.

• Mergesort

• Goal. Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi], replace with sorted subarray a[lo] to a[hi].

Java implementation (Merging)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
  assert isSorted(a, lo, mid); // precondition: a[lo..mid] sorted
  assert isSorted(a, mid+1, hi); // precondition: a[mid+1..hi] sorted
  for (int k = lo; k <= hi; k++)
    aux[k] = a[k];
  int i = lo, j = mid+1;
  for (int k = lo; k <= hi; k++) {
    if (i > mid) a[k] = aux[j++];
    else if (j > hi) a[k] = aux[i++];
    else if (less(aux[j], aux[i])) a[k] = aux[j++];
    else a[k] = aux[i++];
  }
  assert isSorted(a, lo, hi); // postcondition: a[lo..hi] sorted
}

Java implementation (Mergesort)

1
2
3
4
5
6
7

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
  if (hi <= lo) return;
  int mid = lo + (hi - lo) / 2;
  sort(a, aux, lo, mid);
  sort(a, aux, mid+1, hi);
  merge(a, aux, lo, mid, hi);
}

Quicksort

Quicksort

• Basic plan.
  • Shuffle the array.
  • Partition so that, for some j
    • entry a[j] is in place
    • no larger entry to the left of j
    • no smaller entry to the right of j
  • Sort each piece recursively.
• Quicksort partitioning.
  • Repeat until i and j pointers cross.
    • Scan i from left to right so long as (a[i] < a[lo]).
    • Scan j from right to left so long as (a[j] > a[lo]).
    • Exchange a[i] with a[j]
  • When pointers cross.
    • Exchange a[lo] with a[j].

Java code for partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14

private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo, j = hi+1;
    while (true) {
        while (less(a[++i], a[lo]))
            if (i == hi) break;
        while (less(a[lo], a[--j]))
            if (j == lo) break;

        if (i >= j) break;
        exch(a, i, j);
    }
    exch(a, lo, j);
    return j;
}

Quicksort: Java implementation

1
2
3
4
5
6
7
8
9
10
11
12

public class Quick {
    private static int partition(Comparable[] a, int lo, int hi) {}
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }
} 

• Quicksort is not stable.

选择一组数列中的第一个为基准数，置换所有比基准数小的和比基准数大的数字，最后把基准数放到整个数列中它最后该在的位子。递归地把它前后乱序的数列按同样的办法整理好。