0. (not to be done in tut) Write pseudocode for doing a BFS traversal starting from some given node that uses only O(1) additional space for every node. The input is the adjacency matrix of a graph.

1. Show that the worst-case complexity of Find(x) in the Reverse-Tree+Union-by-depth implementation is Theta(n).

Hint: Use a sequence of Union() that creates a balanced binary tree. Then call Find(x) for any x in the last level.

2. Implement a disjoint-set using singly linked lists. Discuss the complexities of MakeSet, Find and Union (try to derive tight bounds by constructing generic examples that meet those bound).

Hint: Depends on implementation. Discuss students' ideas.

3. You want to implement a data structure to maintain an array of bits X[1 ... n] along with these operations.

  (  i) Init() : Initialization. All bits of X are initialized to 0.
  ( ii) Set(i) : Set X[i]=1. It is guaranteed that i <= n-1 so the rightmost bit of X[] is never set.
  (iii) IsSet(i): return X[i]
  ( iv) NextUnset(i): return the next largest smallest j >= i s.t. X[j]=0. This will always return some index. (Think why?)

Show how to implement these using a disjoint-set at the backend.
Hint: Use a disjoint-set "API" to implement these functions. You can add additional fields to the elements and sets but you should be calling the Find/Makeset/Union operations to implement  Set/IsSet/NextUnset and any sort of preprocessing. The data structures do all of the heavy lifting.

4. JE6 Problem 11 (parallel assignment).