In our first meeting, I quizzed the students about their background in
various versions of CS171.  Results:

 * basic sequences (stacks, queues, arrays or linked lists) are done.
   One "Chapter 1" topic is not familiar: union-find.

 * basic comparison sorting (mergesort and quicksort) is done,
   but radixsort needs to be done, probably also the n lg n lower bound.

 * binary search trees have been seen, but not everyone has
   seen a balanced binary search tree, we'll probably do red-black

 * everyone is familiar with the basic big-Oh notation, like
   O(1), O(n), O(n lg n), O(n^2), and so on

 * everyone has heard of the notion of a graph, and most have seen
   some kind of basic graph traversal (either breadth-first-search
   or depth-first search)

 * a majority have seen Dijkstra's algorithm, to find shortest
   paths in a weighted graph

 * a smaller number (70%?) saw binary heaps or priority queues,
   (but then how did you do Dijkstra?).  We'll probably
   review that, then try some other PQ applications.

Based on this, I'll write up a "course intro" handout, with
rough syllabus, for Friday.   That handout will also give the book
and grading information from class today, so I won't repeat it here.
We plan to visit the lab Wednesday, to see if everyone can login.

As a first CS topic, I introduced the union-find data structure, 
looking at pages 218-219 for the figure and the UF API.  
I wrote out the following code:

     UF u = new UF(4);   // create 4 isolated nodes: 0, 1, 2, 3
     u.union(1,3);       // add edge from 1 to 3
     u.union(2,3);       // add edge from 2 to 3
     assert(! u.connected(0,3)); // 0 and 3 are not connected (not yet)
     assert(u.connected(1,2));  // 1 and 2 are connected
     u.union(0,1);       // add edge from 0 to 1
     assert(u.connected(0,3)); // 0 and 3 are connected

I also drew a picture on the board, explaining the above situation.
Actually, I spent more time explaining the Java "assert" function,
which is useful for debugging (you assert expressions that you
believe are true, and Java can check them at runtime, throwing an
exception if an assertion is false).

I proposed how we could implement this: maintain a graph (an adjacency
list for each vertex), and run a graph traversal (like BFS, breadth first
search) each time we want to check whether two vertices are connected.
But then the connected(p,q) method would have worst case running time
O(N+M)  (N = # vertices, M = # edges).   We'll see how to do better next
time.

We also looked at the find(p) method, which should return an int that
identifies the component containing p (typically, it is a vertex
"leader" of the component).   So u.connected(p,q) should always
equal this expression:   u.find(p)==u.find(q)