Coursera: Princeton University

Algorithms

Self learning of Princeton University's Algorithms course in Coursera.

Instructors: Robert Sedgewick, Kevin Wayne

Textbook: Algorithms, 4th

Coursera:

• Algorithms, Part I
• Algorithms, Part II

Schedule

Interview Questions are optional, you should write it if you want a job. Every week has an assignment which requires content of that week and previous weeks.

Part I

Week	Lecture	Textbook	Practice Quiz	Programming Assignments
1	Course Introduction	1.1, 1.2		Project 0: Hello, World
	Union-Find	1.5	Union-Find	Project 1: Percolation
	Analysis of Algorithms	1.4	Analysis of Algorithms
2	Stacks and Queues	1.3	Stacks and Queues	Project 2: Queues
	Elementary Sorts	2.1	Elementary Sorts
3	Mergesort	2.2	Mergesort	Project 3: Collinear
	Quicksort	2.3	Quicksort
4	Priority Queues	2.4	Priority Queues	Project 4: 8 Puzzle
	Elementary Symbol Tables	3.1, 3.2	Elementary Symbol Tables
5	Balanced Search Trees	3.3	Balanced Search Trees
	Geometric Applications of BSTs			Project 5: Kd-Trees
6	Hash Tables	3.4	Hash Tables
	Symbol Table Applications

Part II

Week	Lecture	Textbook	Practice Quiz	Programming Assignments
1	Course Introduction	1.1, 1.2
	Undirected Graphs	4.1	Undirected Graphs
	Directed Graphs	4.2	Directed Graphs	Project 6: WordNet
2

Notes

4.1 Undirected Graphs

Q: Why each edge counted twice in count self-loops ?

public static int numberOfSelfLoops(Graph G)
{
    int count = 0;
    for (int v = 0; v < G.V(); v++)
        for (int w : G.adj(v))
            if (v == w) count++;
    return count/2;     // each edge counted twice
}

A: This depends on the Graph API implementation. Self-loops are inserted twice (since v == w).

public void addEdge(int v, int w)
{
    adj[v].add(w);
    adj[w].add(v);
}

Assignments

Project 0: Hello, World

Implementations of class HelloWorld and class HelloGoodbye are uncessary import algs4.jar.
Thus, CLI use javac and java instead of javac-algs4 and java-algs4.
Note: Knuth’s method, when reading ith word which i is start from 1, not 0.

Project 1: Percolation

In class Percolation, method open() should not open site repeated times. If you get a more larger value, check your open() method whether it open site multiply times and count the repeated times.

Project 2: Queues

For RandomizedQueue.java's deque operation, I swap random item with tail item.
For client part, command below:

java Permutation 3 < distinct.txt

should be:

java-algs4 Permutation 3 < distinct.txt

Project 3: Collinear

General:

1. For Comparable's compareTo() and Comparator's compare(), if not all operators are integers, don't use subtraction and then cast to int (which will cause small real number (positive or negative) to be zero).
2. Don't mutate argument array's content.

FastCollinearPoints:

1. Build a copy of array (since sort is inplace) for correct interation.
2. Make use of stability of sort to avoid invalid segments.
3. If your number of collinear segments is less, consider all points are collinear.

Project 4: 8 Puzzle

Board:

1. Recommend use 2D array instead 1D array to implemnet.
2. twin() method must return same Board every time.
3. Skip blank (since it is not tile). Check that you skip blank in isGoal(), hamming() and manhattan() methods.

Solver:

1. Key problem is to implemnet a class about search node in game tree.
2. You can use stack to store solution for correct move order.

Note: If you want to understand A* algorithm, UC Berkeley's cs188 is a good reference.

Project 5: Kd Trees

I only get 97 scores at this project since (my nearest() method).

1. insert() and contains() are similar as implementation in BST (consider level).
2. range() just like iterate implementation.
3. nearest() only coniders rectangle(s) which would contains closer point (consider using RectHW's distanceSquaredTo() (or distanceTo()) method).