Implement the UNION/FIND algorithm of Section 6.2 using both path compression and the weighted union rule. Count the total number of node accesses required for various series of equivalences to...

Implement the UNION/FIND algorithm of Section 6.2 using both path compression and the weighted union rule. Count the total number of node accesses required for various series of equivalences to determine if the actual performance of the algorithm matches the expected cost of Θ(n log∗ n).

For each of the following recurrences, find and then prove (using induction) an exact closed-form solution. When convenient, you may assume that n is a power of 2. (a) T(n) = T(n − 1) + n/2 for n > 1; T(1) = 1. (b) T(n) = 2T(n/2) + n for n > 2; T(2) = 2.