Princeton Algorithms Notes | Set 1

Posted on | | Visitors

这是 Princeton Algorithms Course 的第二篇笔记
对应的 lecture 是 coursera 上的第二周的内容
包括了 Bags, Stack, Queue, Iterator & Elementary Sort
由于之前我们已经讨论过 Stack 和 Queue，在此不再过多叙述

Iterator

One of the fundamental operations on collections is to process each item by iterating through the collection using Java’s foreach statement

1
2
3
4
5
Stack<String> collection = new Stack<String>();
......
for (String s : collection){
    System.out.println(s);
}

上面的代码等同于如下代码，但显然 foreach statement 更简洁

1
2
3
4
5
Iterator<String> i = collection.iterator();
while (i.hasNext()){
    String s = i.next();
    System.out.println(s);
}

当我们在 implements 数据结构的时候，也要考虑使其继承 Iterable 接口

当然，也要加上异常处理机制
UnsupportedOperationException if a client calls remove()
NoSuchElementException if a client class next() when i is 0

也要注意在代码开头加上 import java.util.Iterator;
因为 Iterator 不在 java.lang 包里面

以下是 Bag 的完整实现

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
import java.util.Iterator;
public class BagDemo<Item> implements Iterable<Item>{
    private Node first;
    private class Node{
	Item item;
	Node next;
    }
    public void add(Item item){ // Same as push() in stack
	Node oldFirst = first;
	first = new Node();
	first.item = item;
	first.next = oldFirst;  
    }
    public Iterator<Item> iterator(){
	return new ListIterator();
    }
    public class ListIterator implements Iterator<Item>{
	private Node current = first;
	public boolean hasNext(){
	    return current != null;
	}
	public void remove(){}
	public Item next(){
	    Item item = current.item;
	    current = current.next;
	    return item;
	}
    }
}

Assignment 2

在 Courser 上第二周里有个编程作业
要求实现 Deques and Randomized Queues
具体的 assignment 要求在这里

下面是我的代码，仅供参考

Deque

Dequeue. A double-ended queue or deque (pronounced “deck”) is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure.

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.util.*;
public class Deque<Item> implements Iterable<Item>{
    private Node first;
    private Node last; 
    private int N;
    private class Node{
	Item item;
	Node prev;
	Node next;
	Node(Item item){  // constructor to create a new node
	    this.item = item;
	}
    }
    public Deque(){
	first = null;
	last = null;
	N = 0;
    }
    public boolean isEmpty(){
	return N == 0;
    }
    public int size(){
	return N;
    }
    public void addFirst(Item item){
	if (item == null){
	    throw new java.lang.IllegalArgumentException();
	}
	Node oldFirst = first;
	first = new Node(item);
	first.next = oldFirst;
	if (isEmpty()) last = first;
	else oldFirst.prev = first;
	N++;
    }
    public void addLast(Item item){
	if (item == null){
	    throw new java.lang.IllegalArgumentException();
	}
	Node oldLast = last;
	last = new Node(item);
	last.prev = oldLast;
	if (isEmpty()) first = last;
	else oldLast.next = last;
	N++;
    }
    public Item removeFirst(){
	if (isEmpty()) {
	    throw new java.util.NoSuchElementException();
	}
	Item result = first.item;
	first = first.next;
	N--;
	if (isEmpty()) last = null;
	else first.prev = null;
	return result;
    }
    public Item removeLast(){
	if (isEmpty()) {
	    throw new java.util.NoSuchElementException();
	}
	Item result = last.item;
	last = last.prev;
	N--;
	if (isEmpty()) first = null;
	else last.next = null;
	return result;
    }
    public Iterator<Item> iterator(){
	return new ListIterator();
    }
    private class ListIterator implements Iterator<Item>{
	private Node current = first;
	public boolean hasNext(){
	    return current != null;
	}
	public void remove(){
	    throw new java.lang.UnsupportedOperationException();
	}
	public Item next(){
	    if (!hasNext()){
		throw new java.util.NoSuchElementException();
	    }
	    Item item = current.item;
	    current = current.next;
	    return item;
	}
    }
    public static void main(String[] args){
	Deque d = new Deque();
	d.addFirst(1);
	d.addFirst(2);
	d.addLast(3);
	d.addLast(4);
	System.out.println(d.size());   // 4
	System.out.println(d.isEmpty());  // false
	Iterator itr = d.iterator();
	while (itr.hasNext()){
	    System.out.print(itr.next() + " ");  // 2 1 3 4
	}
	System.out.println();
    }
}

Randomized queue

Randomized queue. A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure.

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.util.*;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
public class RandomizedQueue<Item> implements Iterable<Item>{ 
    private Item[] a;
    private int N;
    public RandomizedQueue(){
	a = (Item[]) new Object[1];
	N = 0; 
    }
    private void resize(int capacity){
	Item[] temp = (Item[]) new Object[capacity];
	for (int i = 0; i < N; i++){
	    temp[i] = a[i];
	}
	a = temp;
    }
    public boolean isEmpty(){
	return N == 0;
    }
    public int size(){
 	return N;
    }
    public void enqueue(Item item){
	if (item == null){
	    throw new IllegalArgumentException();
	}
	if (N == a.length) {
	    resize(2 * a.length);
	}
	a[N++] = item; 
    }
    public Item dequeue(){
	if (isEmpty()){
	    throw new NoSuchElementException();
	}
	int index = StdRandom.uniform(N);
	Item result = a[index];
	a[index] = a[--N];
	a[N] = null;
	if (N > 0 && N == a.length / 4){
	    resize(a.length / 2);
	}
	return result;
    }
    public Item sample(){
	if (isEmpty()){
	    throw new NoSuchElementException();
	}
	int index = StdRandom.uniform(N);
	return a[index];
    }
    public Iterator<Item> iterator(){
	return new RandomizedQueueIterator();
    }
    private class RandomizedQueueIterator implements Iterator<Item>{
	private int index = 0;
	private int newSize = N;
	private Item[] temp = (Item[]) new Object[N];
	private RandomizedQueueIterator(){
	    for (int i = 0; i < N; i++){
		temp[i] = a[i];
	    }
	}
	public boolean hasNext(){
	    return index < newSize;
	}
	public Item next(){
	    if (!hasNext()){
		throw new NoSuchElementException();
	    }
	    int random = StdRandom.uniform(newSize);
	    Item item = temp[random];
	    if (random != newSize - 1){
		temp[random] = temp[newSize - 1];
	    }
	    newSize--;
	    temp[newSize] = null;
	    return item;
	}
	public void remove() {
            throw new UnsupportedOperationException();
        }
    }
	
    public static void main(String[] args){
	RandomizedQueue<Integer> q = new RandomizedQueue<Integer>();
		
	q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5);
        q.enqueue(6);
        q.enqueue(7);
        q.enqueue(8);
        q.enqueue(9);
        q.dequeue();
        q.dequeue();
 
        StdOut.println("Output: ");
        for (Integer x : q) {
            StdOut.print(x + " ");  // 5 6 8 4 1 7 2
        }
        StdOut.println();
        StdOut.println(q.size()); // 7
    }
}

值得一提的是，在上面的代码中，我使用了 Princeton 的 Java library 里的方法
StdOut.println() 和 StdRandom.uniform()
在 Eclipse 中，需要把下载下来的 algs.jar 包导入到 build path 中
具体操作如下：project -> properties -> java build path -> Add Jar

整个代码的实现思路还是很简单的，值得注意的是 Iterator 里的 next() 方法
当我们随机取出一个数后，做了如下操作：
把最后一个元素填补到该取出的元素索引那里
再把最后一个元素赋值为 null

Permutation client

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* Write a client program Permutation.java that takes a command-line integer k; reads in a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once.*/
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Permutation {
    public static void main(String[] args){
	RandomizedQueue<String> q = new RandomizedQueue<String>();
		
	int k = Integer.parseInt(args[0]);
		
	while (!StdIn.isEmpty()){
	    q.enqueue(StdIn.readString());
	}
		
	while (k > 0){
	    StdOut.print(q.dequeue()  + " ");
	    k--;
	}
    }
}

Elementary Sort

Elementary Sort 这一节 lecture 里讲了 Selection Sort，Insertion Sort，ShellSort，Shuffling 等不同的 sort algorithms
下面就来一一分析

Selection Sort

Selection Sort 作为最基本的 sort algorithm，它的逻辑也是很简洁明了的
即遍历整个数组，在余下的数组元素中找到最小的，于此时的第一个元素交换
下面给出了它的伪代码

1
2
3
4
5
6
repeat (numOfElements - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position

Java 代码实现如下

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
public class SelectionSort{
    void sort(int[] array){
	int n = array.length;
	for (int i = 0; i < n; i++){
	    int min = i;
	    for (int j = i + 1; j < n; j++){
		if (array[j] < array[min]) min = j;
	    }
	    int temp = array[min];
	    array[min] = array[i];
	    array[i] = temp;
	}
    }
    void printArray(int[] array){
	for (int i : array){
	    System.out.print(i + " ");
	}
	System.out.println();
    }
    public static void main(String[] args){
	SelectionSort s = new SelectionSort();
	int[] array = {9, 8, 3, 1, 4 ,6 , 7, 2};
	s.sort(array);
	System.out.println("Sorted array: ");
	s.printArray(array);    // 1 2 3 4 6 7 8 9 
    }
}

Time Complexity: O(n^2)

proof: For each i fromm 0 to N - 1, there is one exchange and N - 1 - i copmares, so the totals are N exchanges and (N-1) + (N-2) + (N-3) + … + 0 = N(N-1)/2 ~ N^2/2 compares

Auxiliary Space: O(1)

Insertion Sort

关于 Insertion Sort 的详细讨论在之前的 MIT 6.006 的一篇笔记中已经讨论过了
在此不再多说，具体地址在这里

Shellsort

Shellsort 类似于 Insertion sort，不同点在于 Insertion sort 一个个地交换元素
直到元素在合适地地方为止
而 Shellsort 允许我们间隔 t 个元素来进行这样的比较和交换
称之为 t-sorted, 同时不断减小 t 的值，直到1为止

We make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.

Shellsort 可视化演示
我们一般选取 t = n / 3 + 1

Java 代码实现如下

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
public class Shellsort{
    void sort(int[] a){
	int n = a.length;
	// 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ...
	int h = 1;
	while (h < n / 3) h = 3 * h + 1;
	while (h >= 1){
	    // h-sort the array
	    for (int i = h; i < n; i++){
		for (int j = i; j >= h && a[j] < a[j - h]; j -= h){
		    int temp = a[j];
		    a[j] = a[j - h];
		    a[j - h] = temp;
		}
	    }
	    h /= 3;
	}
    }
    void printArray(int[] a){
	for (int i : a){
	    System.out.print(i + " ");
	}
	System.out.println();
    }
    public static void main(String[] args){
	int[] array = {9, 8, 3, 1, 6, 2, 7, 4, 5};
	Shellsort s = new Shellsort();
	s.sort(array);
	System.out.println("Sorted array: ");
	s.printArray(array); // 1 2 3 4 5 6 7 8 9 
    }
}

对于该算法的时间分析比较复杂
根据 t 的取值不同，花费的时间也不同
在学术界关于 Shellsort 的讨论仍然没有明确的结果
在此不过多叙述

Shuffling

  1. In iterator i, pick integer r between 0 and i uniformly at random.
  2. Swap a[i] and a[r]

Linear time shuffling algorithms

1
2
3
4
5
6
7
8
9
10
public static void shuffle(Object[] a){
    int N = a.length;
    for (int i = 0; i < N; i++){
	int r = StdRandom.uniform(i + 1);    // between 0 and 1
	Object temp = a[i];  //  exchange a[i] and a[r]
	a[i] = a[r]; 
	a[r] = temp;
    }
}

Convex Hull

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

Equivalent definations:

  1. Smallest convex set containging all the points.
  2. Smallest area convex polygon enclosing the points.
  3. Convex polygon enclosing the points, whose vertices are points in set.

Convex hull output:
Sequence of vertices in counterclockwise order

谢谢你请我吃糖果：）