Chapter #8 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 7 exercises:

 
8.1 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. - Get solution

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

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

 

 8.8 Prove that for the mazes generated by the algorithm in Section 8.7, the path from

the starting to ending points is unique. - Get solution

8.9 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. - Get solution

8.10 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(MlogN) 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. - Get solution

8.11 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)). - Get solution

8.12 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. - Get solution

8.14 Prove that if unions are done by size and path compression is performed, the worstcase

running time is O(Mα(M,N)). - Get solution

8.16 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)). - Get solution