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).