This problem is related to disjoint set operations. Assume that we are

using union by rank and find with path compression. Suppose that you are given a disjoint

set structure described by the following array representation.

i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|

A |-3 | 1 | 1 | 3 | 1 | 5 | 5 | 7 |-3 | 9 | 9 | 11| 9 | 13| 13| 15|

(a) Suppose that you are starting with 16 disjoint sets obtained by

FOR i=1 to 16 DO make-set(i)

There are multiple sequences of find-set and union operations that will change these 16

disjoint sets to the one listed in the above. Find one such sequence, and list the last two

union operations in your sequence.

(b) Write the resulting array representation of the disjoint set structure after applying

union(2, 10) to the given disjoint set structure.

(c) Write the resulting array representation of the disjoint set structure after applying

union(8, 14) to the given disjoint set structure (not the one after your operation).

(d) Assume that you are dealing with n elements and m disjoint set operations including

n make-set operations. Use asymptotic notation to denote the total time complexity of

these m operations if union is by rank and find is with path compression.