Algorithms I, Princeton University, P1

For me, great algorithms are the poetry of computation. — Donald Knuth

Presented by Robert Sedgwick & Kevin Wayne，普林斯顿大名鼎鼎的算法课程，在 Coursera 上接近满分的评价：这么多 buff 加身的神课，不认真刷一下都对不起我自己。

我想通过学习这门课得到什么？

• 想将之前参加 OI 掌握的算法知识系统化；
• 采用 Java 进行授课，想通过这门课入门这个著名的纯 OOP 语言；
• 这门课有 10 个超高质量的 Projects，实际问题背景，丰富的测试样例，竟然还配有教授工业级别高效实现的源码！即使抄下来做板子都是十分宝贵的收获。

关于笔记的组织形式，曾经想了很多种方案，但最终都否决了。本课的大纲遵循一种很自然的，难以分类的顺序；如果强制割裂开来，会显得很 inconsistent。于是最终还是采用了最简单的时间顺序记录；除了 P4，它记录的是这门课中包含的 Java 语言知识。

另，本课程 projects 的代码实现存放在 ThisisXXZ/Algorithms-Princeton - GitHub 中，仅供参考。

这是 Algorithms I & II, Princeton 系列笔记的 P1 部分。这一节将介绍：

• 并查集。
• 算法复杂度分析的基本方法与 notations。
• 栈与队列——链表与动态数组实现。
• \(\sim N^2\) 的基础排序——选择排序，插入排序，希尔排序 (最优可达 \(\sim N\log{N}\))。

  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.

Union-Find

把并查集作为课程中第一个介绍的算法实在是独具匠心。

我现在还记得第一次学到并查集时的惊喜：它像是一篇精彩的短文，读完让人大呼过瘾。其实现是那么的精巧而简洁，以至于在之后在学习 BST，LCT 等复杂晦涩的算法时，我时常会怀念这种 Eureka 的感觉。

Problem Model: Dynamic Connectivity

Given a set of \(N\) objects.

• Union command: connect two objects.
• Find/connected query: is there a path connecting the two objects?

Primitive method: Given a unique \(id\) for each connected component.

• Quick-Find: \(O(n)\) updates the \(id\) as an array. \(O(1)\) query by checking \(id\).
• Quick-Union: \(O(1)\) updates the \(id\) as a forest. \(O(n)\) query by checking the \(id\) of root.

Improvements

Improvement 1: Weighting

• Modify Quick-Union to avoid tall trees.
• Keep track of size of each tree (number of objects).
• Balance by linking the root of smaller tree to the root of larger tree. (Reasonable alternatives: union by height or "rank")

Proposition. Depth of any node \(x\) is at most \(\lg{N}\).

Pf. When does depth of \(x\) increase? Increase by \(1\) when tree \(T_1\) containing \(x\) is merged into another tree \(T_2\).

• The size of the tree containing \(x\) at least doubles since \(|T_2|\geq |T_1|\).
• Size of tree containing \(x\) can double at most \(\lg N\) times.

Weighting flattened the tree greatly

Improvement 2: path compression

Just after computing the root of \(p\), set the \(id\) of each examined node to point of that root.

Code Implementation

Weighted quick-union with path compression: in practice, WQUPC is linear.

public class UF {
    
    private int[] parent;    // parant[i] = parent of i
    private byte[] rank;     // we apply union by rank here (never more than 31)
    private int count;       // numbers of connected components
    
    public UF(int n) {
        if (n < 0)    throw new IllegalArgumentException();
        count = n;
        parant = new int[n];
        rank = new byte[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];    // path compression by halving
            p = parent[p];
        }
        return p;
    }
    
    public int count() {
        return count;
    }
    
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)    return;
        
        if      (rank[rootP] < rank[rootQ])    parent[rootP] = rootQ;
        else if (rank[rootP] > rank[rootQ])    parent[rootQ] = rootP;
        else {
            parent[rootQ] = rootP;
            ++rank[rootP];
        }
        --count;
    }
    
    public void validate(int p) {
        int n = parent.length;
        if (p < 0 || p >= n) {
            throw new IllegalArgumentException("Index is not between 0 and " + (n-1));
        }
    }
    
    public static void main(String[] args) {
        int n = StdIn.readInt();
        UF uf = new UF(n);
        while (!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            if (uf.find(p) == uf.find(q))    continue;
            uf.union(p, q);
            StdOut.println(p + " " + q);
        }
        StdOut.println(uf.count() + " components");
    }
}

Analysis of Algorithms

学到这里才发现之前用 Big-Oh notation \(O(n)\) 描述时间复杂度是一个常见的误区......！

Mathematical Models

The total running time of an algorithm is the sum of cost \(\times\) frequency for all operations. In principle, we could always develop an accurate mathematical models for a particular algorithm.

However, taking exactly all operations into consideration seems too tedious.

Simplification 1: cost model

Cost model. Use some basic operations as a proxy for running time.

When a proper cost model is chosen, other operations could be ignored.

choose the operation with the highest frequency as the cost model

Simplification 2: tilde notation

We use tilde notation \(\sim\) to estimate running time (or memory) as a function of input size \(N\). It will ignore all lower-order terms.

• When \(N\) is large, lower-order terms are negligible.
• When \(N\) is small, we simply don't care.

Technically, \(f(N)\sim g(N)\) means \(\lim_{N\to\infty} \frac{f(N)}{g(N)}=1\).

Order-of-Growth Classifications

Good news. the small set of functions \(1,\log N,N,N\log N,N^2,N^3\) and \(2^N\) suffices to describe order-of-growth of typical algorithms.

Here are the common order-of-growth classifications:

• constant \(1\): statement
• logarithmic \(\log N\): divide in half
• linear \(N\): loop
• linearithmic \(N\log N\): divide and conquer
• quadratic \(N^2\): double loops
• cubic \(N^3\): triple loops
• exponential \(2^N\): exhaustive search

Typically, better order of growth \(\to\) faster in practice.

Commonly Used Notations

notation	provides	used to
Tilde \(\sim\)	leading term	provide approximate model
Big Theta \(\Theta(\cdot)\)	asymptotic growth rate	classify algorithms
Big Oh \(O(\cdot)\)	\(\Theta(\cdot)\) and smaller	develop upper bounds
Big Omega \(\Omega(\cdot)\)	\(\Theta(\cdot)\) and larger	develop lower bounds

Common mistake. Interpreting big-Oh as an approximate model.

Example: 1-SUM problem \(=\) "Is there a 0 in the array?"

• Upper bound. A specific algorithm.

  Brute-force algorithm for 1-SUM: Look at every array entry. Running time of the optimal algorithm for 1-SUM is \(O(N)\).

• Lower bound. Proof that no algorithm can do better.

  Have to examine all \(N\) entries (any unexamined one might be \(0\)). Running time of the optimal algorithm for 1-SUM is \(\Omega(N)\).

If for a specific problem, upper bound \(O(N)=\) lower bound \(\Omega(N)\), we say there exists an optimal algorithm with \(\Theta(N)\) running time.

Algorithm design aims to reduce the gap between upper bound \(O(N)\) and lower bound \(\Omega(N)\).

Stack & Queue

No need to give a detailed introduction on these two famous data structures. We will focus on how to implement them in two different approaches - linked lists or resizing arrays.

• Approach 1. linked lists. (ez)
• Approach 2. resizing arrays.

Resizing-Array Implementation

Consider an array-based stack. The implementation is trivial; however, we need to know the size \(N\) of the input data to avoid stack overflow.

Therefore, we introduce the resizing arrays to this problem: the resizing arrays grow and shrink dynamically according to the current data size.

• How to grow array? (operation push()) If array is full, create a new array of twice (repeated doubling) the size, and copy items.
• How to shrink array? (operation pop()) If array is one-quarter full, create a new array of half the size, and copy items.

Note that we shrink array when it is \(1/4\) full instead of \(1/2\) full to avoid the worst case: push-pop-push-pop...sequence when array is full.

It is proven that the amortized running time of a single push/pop is constant. (in particular, \(3\))

Note that the array size grow exponentially: \(2^t\) for t-th growth

Linked Lists Versus Resizing Arrays

implementation/cost	time	space
Linked Lists	Every operation takes constant time in the worst case.	Use extra space to deal with the links.
Resizing Arrays	Every operation takes constant amortized time.	Less wasted space.

Code Implementation

Here is a resizing-array implementation for a queue.

public class ResizingArrayQueue<Item> implements Iterable<Item> {
    // initial capacity of underlying resizing array
    private static final int INIT_CAPACITY = 8;

    private Item[] q;       // queue elements
    private int n;          // number of elements on queue
    private int first;      // index of first element of queue
    private int last;       // index of next available slot

    // Initializes an empty queue.
    public ResizingArrayQueue() {
        q = (Item[]) new Object[INIT_CAPACITY];
        n = 0;
        first = 0;
        last = 0;
    }

    // return true if this queue is empty; false otherwise
    public boolean isEmpty() {
        return n == 0;
    }

    // Returns the number of items in this queue.
    public int size() {
        return n;
    }

    // resize the underlying array
    private void resize(int capacity) {
        assert capacity >= n;
        Item[] copy = (Item[]) new Object[capacity];
        for (int i = 0; i < n; i++) {
            copy[i] = q[(first + i) % q.length];
        }
        q = copy;
        first = 0;
        last  = n;
    }

    // Adds the item to this queue.
    public void enqueue(Item item) {
        // double size of array if necessary and recopy to front of array
        if (n == q.length) resize(2*q.length);   // double size of array if necessary
        q[last++] = item;                        // add item
        if (last == q.length) last = 0;          // wrap-around
        n++;
    }


    // Removes and returns the item on this queue that was least recently added.
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = q[first];
        q[first] = null;                            // to avoid loitering
        n--;
        first++;
        if (first == q.length) first = 0;           // wrap-around
        // shrink size of array if necessary
        if (n > 0 && n == q.length/4) resize(q.length/2);
        return item;
    }

    // Returns the item least recently added to this queue.
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return q[first];
    }


    public Iterator<Item> iterator() {
        return new ArrayIterator();
    }

    // an array iterator, from first to last-1
    private class ArrayIterator implements Iterator<Item> {
        private int i = 0;

        public boolean hasNext() {
            return i < n;
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = q[(i + first) % q.length];
            i++;
            return item;
        }
    }

    public static void main(String[] args) {
        ResizingArrayQueue<String> queue = new ResizingArrayQueue<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) queue.enqueue(item);
            else if (!queue.isEmpty()) StdOut.print(queue.dequeue() + " ");
        }
        StdOut.println("(" + queue.size() + " left on queue)");
    }

}

Elementary Sorts

获益良多，对 \(\sim N^2\) 的基础排序算法 (插排，希尔排序) 有了新的认识。之前一直觉得有快排就够了 (N 方的排序算法是什么臭鱼烂虾)，学完之后才发现这样的想法是多么傲慢。这些算法里蕴含的排序思想，和无数计算机科学家 (包括教授 Sedgewick) 尝试改进优化所做的努力，都是难能可贵的。

排序算法在 Java 中的实现离不开 Comparable 接口。有关这部分的内容 (包括下文所用到的 less 与 exch 辅助方法) 将在 P4 中进行记录。

Selection Sort

In iteration \(i\), find index \(min\) of smallest remaining entry. Then swap \(a_i\) and \(a_{min}\).

public static void sort(Comparable[] a) {
    int N = a.length;
    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);
    }
}

Proposition. Selection sort uses \(0+1+...+(N-1)\sim N^2/2\) compares and \(N\) exchanges.

The running time is intensive to input: it takes quadratic time even if input is sorted.

Knuth's shuffle is structurally similar to selection sort. It is used to generate random shuffles.

Insertion Sort

In iteration \(i\), swap \(a_i\) with each larger entry to its left.

public static void sort(Comparable[] a) {
    int N = a.length;
    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;
        }
}

Insertion sort is NOT intensive to input.

• Best case. ascending arrays: it makes \(N-1\) compares and \(0\) exchanges.
• Worst case. descending arrays: it makes \(\sim \frac{1}{2}N^2\) compares and \(\sim \frac{1}{2}N^2\) exchanges.

Note that for partially-sorted arrays, insertion sort runs in linear time.

This is because number of exchanges equals the number of inversions, and numbers of compares \(=\) exchanges \(+(N-1)\).

Def 1. An inversion is a pair of keys that are out of order.

Def 2. An array is partially sorted if the number of inversions is \(\leq cN\).

Shellsort

Idea. Move entries more than one position at a time by \(h\)-sorting the array.

an \(h\)-sorted array is \(h\) interleaved sorted subsequences

Shellsort. [Shell 1959] Repeatedly \(h\)-sort the array with a decreasing sequence of values of \(h\).

We use insertion sort with stride length \(h\) to \(h\)-sort an array. why choosing insertion sort:

• Big increments \(\to\) small subarray.
• Small increments \(\to\) nearly in order. (insertion sort is fast when array is partially sorted)

Note the fact that a \(g\)-sorted array remains \(g\)-sorted after \(h\)-sorting it.

An efficient shellsort scheme depends on a proper increment sequence.

• \(3x+1\). (most commonly used) \(1,4,13,40,121,364,...\)
• Sedgewick. (tough to beat in empirical studies) \(1,5,19,41,109,...\)

The worst-case number of compares used by shellsort with the \(3x+1\) increments is \(O(N^{3/2})\).

However, accurate model for shellsort has NOT yet been discovered. Maybe some better increment sequences are still left for discover......!

public class Shell {
    public static void sort(Comparable[] a) {
        int N = a.length;
        
        int h = 1;
        while (h < N/3)    h = 3 * h + 1;     // generate 3x+1 increment sequence
        
        while (h >= 1) {                      // h-insertion sort
            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 /= 3;
        }
    }
}

Also note that though shellsort uses insertion sort to \(h\)-sort the array, it is NOT stable.

A stable sort preserves the relative order of items with equal keys.

Insertion sort and merge sort are stable; Selection sort and shellsort are not.

Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info:

Algorithms, Part 1, Princeton University. Lecturer: Robert Sedgewick & Kevin Wayne.

Course textbook:

Algorithms (4th edition), Sedgewick, R. & Wayne, K., (2011), Addison-Wesley Professional, view