2. Disjoint Sets ADT Disjoint Sets (DS with operations MakeSet, Union and Find) implemented by trees with Union by rank and Find with path compression have almost constant (but growing) amortized complexity per operation. Binomial trees are defined as follows: B0 has one node, Bi+1 consists of a Bi whose root has another Bi as a principal subtree. 1. Prove that the amortized complexity of DS with arbitrary Union (no rank involved) and Find with path compression is constant when all Union operations precede any Find operation. 2. Consider DS with arbitrary Union and Find with path compression and no constraint on the string of operations. Prove that the amortized complexity of this implementation is (log n) by first building (by a series of arbitrary Unions) a DS S with n = 2k1 elements as a Binomial Tree of rank k 1 and then iterating the following string of operations: {S:=Union(S, MakeSet(i)), Find(j)}, where i varies from n/2 + 1 to n and j is the deepest node in S. 3. The handout linked from the news page (see above) defines the Depth Determination problem, where an efficient solution via non-isomorphic representation improves the amortized complexity of operation FIND-DEPTH from linear to almost constant. (a) Show how to modify Find to implement FIND-DEPTH. Your implementation should perform path compression, and its running time should be linear in the length of the find path. Make sure that your implementation updates pseudodistances correctly. (b) Show how to implement GRAFT(r, v), which combines the sets containing r and v (these sets are Find(r) and Find(v)), by modifying the UNION procedure. Make sure that your implementation updates pseudo-distances correctly. Note that the root of a set Si is not necessarily the root of the corresponding tree Ti .

2. Disjoint Sets ADT Disjoint Sets (DS with operations MakeSet, Union and Find) implemented by trees with "Union by rank" and "Find with path compression" have almost constant (but grow- ing) amortized complexity per operation Binomial trees are defined as follows: Bo has one node Bi+1 consists of a Bi whose root has another Bi as a principal subtree. 1. Prove that the amortized complexity of DS with arbitrary Union (no rank involved) and Find with path compression is constant when all Union operations precede any Find operation 2. Consider DS with arbitrary Union and Find with path compression and no constraint on the string of operations. Prove that the amortized complexity of this implemen- tation is 2 (log n) by first building (by a series of arbitrary Unions) a DS S with m 32 k-1 elements as a Binomial Tree of rank k 1 and then iterating the follow ing string of operations {S: Union (S, Makeset (i)), Find(j) where i varies from n/2 1 to n and j is the deepest node i S 3. The handout linked from the news page (see above) defines the Depth Determination problem, where an efficient solution via non-isomorphic representation improves the amortized complexity of operation FIND-DEPTH from linear to almost constant. (a) Show how to modify Find to implement FIND-DEPTH. Your implementation should perform path compression, and its running time should be linear in the length of the find path. Make sure that your implementation updates pseudo- distances correctly. (b) Show how to implement GRAFT(r, v which combines the sets containing T and v ese sets are Find (r) and Find (v), by modifying the UNION procedure Make sure that your implementation updates pseudo-distances correctly. Note that the root of a set Si is not necessarily the root of the corresponding tree Ti 2. Disjoint Sets ADT Disjoint Sets (DS with operations MakeSet, Union and Find) implemented by trees with "Union by rank" and "Find with path compression" have almost constant (but grow- ing) amortized complexity per operation Binomial trees are defined as follows: Bo has one node Bi+1 consists of a Bi whose root has another Bi as a principal subtree. 1. Prove that the amortized complexity of DS with arbitrary Union (no rank involved) and Find with path compression is constant when all Union operations precede any Find operation 2. Consider DS with arbitrary Union and Find with path compression and no constraint on the string of operations. Prove that the amortized complexity of this implemen- tation is 2 (log n) by first building (by a series of arbitrary Unions) a DS S with m 32 k-1 elements as a Binomial Tree of rank k 1 and then iterating the follow ing string of operations {S: Union (S, Makeset (i)), Find(j) where i varies from n/2 1 to n and j is the deepest node i S 3. The handout linked from the news page (see above) defines the Depth Determination problem, where an efficient solution via non-isomorphic representation improves the amortized complexity of operation FIND-DEPTH from linear to almost constant. (a) Show how to modify Find to implement FIND-DEPTH. Your implementation should perform path compression, and its running time should be linear in the length of the find path. Make sure that your implementation updates pseudo- distances correctly. (b) Show how to implement GRAFT(r, v which combines the sets containing T and v ese sets are Find (r) and Find (v), by modifying the UNION procedure Make sure that your implementation updates pseudo-distances correctly. Note that the root of a set Si is not necessarily the root of the corresponding tree Ti