CS323 notes for January 20 (second meeting).

In about a week, we'll have a course website here:
    http://mathcs.emory.edu/~cs323000/
Until then, a few things are available here:
    http://mathcs.emory.edu/~mic/cs323/  
In particular, today's files are under share/0120/.

We'll make a short "group visit" to the lab on Friday (2/2) rather
than Wednesday (1/25), since another class has reserved Wednesday.
We'll check that you can all login, and find the tools you need.
Before visiting the lab, please do the following:
     * Visit enid.emory.edu
     * Click "ENID Access", and login with your Emory NetID (ENID).
     * Click "Select UNIX/Linux Login Shell", and make sure "bash"
       is selected (not "csh" or "ksh").  Save.
     * [optional] Setup your email forwarding, too.

No homework or formal syllabus yet.  Just based on our discussion
last time, I propose this informal list:

   * union-find (Section 1.5, today)
   * sorting lower bound, binary heap (review) 
   * applications: heapsort, multiway merge
   * balanced binary search trees (review, 2-3, red-black)
   * simple hashing (chaining), perfect hashing (cuckoo, outside book)
   * DFS/BFS review and applications (strong connectivity, cycle detection)
   * MST algortithms (Kruskal and Prim)
   * shortest paths (Dijkstra review, Bellman-Ford)
   * LSD and MSD radix sort for strings (beating the lower bound)
   * tries (in particular TSTs)
   * substring search (at least Knuth-Morris-Pratt, maybe the others) 
   * B-trees (search trees optimized for on-disk storage)
   * network flow problems (optimization)

Optional (if we have enough time):
   * compression, regular expressions
   * event-driven simulations
   * suffix arrays
   * persistent data structures (outside book)
   * multi-threading issues (outside book, Java libs)
   * linear programming (LP reductions, outside the book)
   
Note our textbook has an excellent website:
    http://algs4.cs.princeton.edu/home/
We'll use these materials to discuss union-find today:
    15DemoQuickUnion.mov   -- demo of quick-union
    15UnionFind.pdf        -- book-based lecture slides

Both are in today's directory (share/0120/).  We can also run the book
code examples locally, but it is a bit tricky for now:

mic@caribou:~/http/cs323/share/book$ java -cp stdlib.jar:. UF < tinyUF.txt
4 3
3 8
6 5
9 4
2 1
5 0
7 2
6 1
# components: 2
mic@caribou:~/http/cs323/share/book$