please help with this question. Please show steps

1. (23 pts: 5 4 4 2 8) This problem is about disjoint set operations. Suppose you are given the below forest representation of a disjoint set data structure. Arrows from a node point to its parent (u u.), and the rank of each disjoint set's representative is given. The ranks of all nodes were initially 0 when MAKE-SET was called 16 times to create the node. We use union by rank and find with path compression where applicable. Rank of node 1 3 Rank of node 9 3 2 3 10 11 13 4 12 14 15 16 (a) After calling the MAKE-SET operations, the forest above was created by calling a sequence of FIND-SET and UNION operations. What are the last two union operations in this sequence that will result in the above data structure? Note that you may need to find a longer series of operations leading to this data structure (there are actually multiple possibilities!), but you are asked to provide only the last two operations in your sequence, which must be UNION calls. Format your answer like so: UNION(a, b), UNION(C, a) where a, b, c, and dare the nodes in the UNION calls. (b) Draw the resulting forest representation of the disjoint set data structure after applying the following operation: UNION(2, 10). Label the rank of the representative node. (c) Draw the resulting forest representation of the disjoint set data structure after applying the following operation: UNION(8, 14). (Apply this to the original given data structure, not the one computed in part (b)). Label the rank of the representative node. (d) Assume that we 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 by rank is used with find with path compression (e) The below program creates a number of disjoint sets and then performs operations on them. For the two lines that are starred, draw the forest representation of the disjoint set data structure at that line (in other words, you'll draw two versions of the data structure, one for each starred line). Label the rank of the representative node(s) in your forest. for i 1 to 18 do MAKE-SET() for i 1 to 17 (step size - 2) do UNION(i + 1, i) fori 1 to 15 (step size -3) do UNION(i, i + 2) UNION(5, 13) UNION(10,15) UNION(4, 10) // draw the disjoint sets at this point FIND-SET(3) FIND-SET(12) // draw the disjoint sets at this point 1. (23 pts: 5 4 4 2 8) This problem is about disjoint set operations. Suppose you are given the below forest representation of a disjoint set data structure. Arrows from a node point to its parent (u u.), and the rank of each disjoint set's representative is given. The ranks of all nodes were initially 0 when MAKE-SET was called 16 times to create the node. We use union by rank and find with path compression where applicable. Rank of node 1 3 Rank of node 9 3 2 3 10 11 13 4 12 14 15 16 (a) After calling the MAKE-SET operations, the forest above was created by calling a sequence of FIND-SET and UNION operations. What are the last two union operations in this sequence that will result in the above data structure? Note that you may need to find a longer series of operations leading to this data structure (there are actually multiple possibilities!), but you are asked to provide only the last two operations in your sequence, which must be UNION calls. Format your answer like so: UNION(a, b), UNION(C, a) where a, b, c, and dare the nodes in the UNION calls. (b) Draw the resulting forest representation of the disjoint set data structure after applying the following operation: UNION(2, 10). Label the rank of the representative node. (c) Draw the resulting forest representation of the disjoint set data structure after applying the following operation: UNION(8, 14). (Apply this to the original given data structure, not the one computed in part (b)). Label the rank of the representative node. (d) Assume that we 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 by rank is used with find with path compression (e) The below program creates a number of disjoint sets and then performs operations on them. For the two lines that are starred, draw the forest representation of the disjoint set data structure at that line (in other words, you'll draw two versions of the data structure, one for each starred line). Label the rank of the representative node(s) in your forest. for i 1 to 18 do MAKE-SET() for i 1 to 17 (step size - 2) do UNION(i + 1, i) fori 1 to 15 (step size -3) do UNION(i, i + 2) UNION(5, 13) UNION(10,15) UNION(4, 10) // draw the disjoint sets at this point FIND-SET(3) FIND-SET(12) // draw the disjoint sets at this point