3. 110 pts] Consider the following sequence of Union/Find operations on 12 elements: U(1.2), U(23), F), U(7.5), U(8,s), U(13,5), F(7), 64), U53), U3,4) F(8), F3), U(12.10), U(10.9), U9.11), F(12) With the weighting rule Note: Recall that without the weighting rule Union(x, y) is defined as PARENT if x and y have the same weight, then also let PARENT[x] y y. a. Show the resulting trees when using neither the weighting rule nor the collapsing rule. b. Show the resulting trees when using only the weighting rule c. Show the resulting trees when using only the collapsing rule. d. Show the resulting trees when using both the weighting rule and the collapsing rule. 4. 110 pts] Consider the following game: I think of a positive number n, which you are to determine by guessing numbers and being told whether each guess is too high or too low or is n. There is no apriori upper bound on n -I am free to pick any n Explain your answer Give a strategy for determining n using at most 2log n+c guesses (c is a constant). (include an explanation of the number of guesses that it uses). 3. 110 pts] Consider the following sequence of Union/Find operations on 12 elements: U(1.2), U(23), F), U(7.5), U(8,s), U(13,5), F(7), 64), U53), U3,4) F(8), F3), U(12.10), U(10.9), U9.11), F(12) With the weighting rule Note: Recall that without the weighting rule Union(x, y) is defined as PARENT if x and y have the same weight, then also let PARENT[x] y y. a. Show the resulting trees when using neither the weighting rule nor the collapsing rule. b. Show the resulting trees when using only the weighting rule c. Show the resulting trees when using only the collapsing rule. d. Show the resulting trees when using both the weighting rule and the collapsing rule. 4. 110 pts] Consider the following game: I think of a positive number n, which you are to determine by guessing numbers and being told whether each guess is too high or too low or is n. There is no apriori upper bound on n -I am free to pick any n Explain your answer Give a strategy for determining n using at most 2log n+c guesses (c is a constant). (include an explanation of the number of guesses that it uses)