The disjoint sets analysis in Section 8.6 can be refined to provide tight bounds

Show the result of the following sequence of instructions: union(1,2), union(3,4), union(3,5), union(1,7), union(3,6), union(8,9), union(1,8), union(3,10), union (3,11), union(3,12), union(3,13), union(14,15), union(16,0), union(14,16), union (1,3), union(1, 14) when the unions are: a. Performed arbitrarily. b. Performed by height. c. Performed by size.

For each of the trees in the previous exercise, perform a find with path compression on the deepest node.

Write a program to determine the effects of path compression and the various unioning strategies. Your program should process a long sequence of equivalence operations using all six of the possible strategies.

Show that if unions are performed by height, then the depth of any tree is O(logN).

Suppose f(N) is a nicely defined function that reduces N to a smaller integer. What is the solution to the recurrence T(N) = N f(N)T(f(N)) + N with appropriate initial conditions?

a. Show that if M = N2, then the running time of M union/find operations is O(M). b. Show that if M = N logN, then the running time of M union/find operations is O(M). c. Suppose M = (N log logN). What is the running time of M union/find operations? d. Suppose M = (N log N). What is the running time of M union/find operations?

Tarjans original bound for the union/find algorithm defined (M,N) = min{i 1   (A (i, M/N) > logN)}, where A(1, j) = 2j j 1 A(i, 1) = A(i 1, 2) i 2 A(i, j) = A(i 1, A(i, j 1)) i, j 2 Here, A(m, n) is one version of the Ackermann function. Are the two definitions of asymptotically equivalent?

Prove that for the mazes generated by the algorithm in Section 8.7, the path from the starting to ending points is unique.

Design an algorithm that generates a maze that contains no path from start to finish but has the property that the removal of a prespecified wall creates a unique path.

Suppose we want to add an extra operation, deunion, which undoes the last union operation that has not been already undone. a. Show that if we do union-by-height and finds without path compression, then deunion is easy and a sequence of M union, find, and deunion operations takes O(M logN) time. b. Why does path compression make deunion hard? c. Show how to implement all three operations so that the sequence of M operations takes O(M logN/log logN) time.

Suppose we want to add an extra operation, remove(x), which removes x from its current set and places it in its own. Show how to modify the union/find algorithm so that the running time of a sequence of M union, find, and remove operations is O(M(M,N)).

Show that if all of the unions precede the finds, then the disjoint set algorithm with path compression requires linear time, even if the unions are done arbitrarily

Prove that if unions are done arbitrarily, but path compression is performed on the finds, then the worst-case running time is (M logN).

Prove that if unions are done by size and path compression is performed, the worstcase running time is O(M(M,N))

The disjoint sets analysis in Section 8.6 can be refined to provide tight bounds for small N. a. Show that C(M,N, 0) and C(M,N, 1) are both 0. b. Show that C(M,N, 2) is at most M. c. Let r 8. Choose s = 2 and show that C(M,N,r) is at most M + N.

Suppose we implement partial path compression on find(i) by making every other node on the path from i to the root link to its grandparent (where this makes sense). This is known as path halving. a. Write a procedure to do this. b. Prove that if path halving is performed on the finds and either union-by-height or union-by-size is used, the worst-case running time is O(M(M,N)).

Write a program that generates mazes of arbitrary size. Use Swing to generate a maze similar to that in Figure 8.25.