Exercise 4 (for week of Mar 15-19) (A) Recall the running time of the DisjointSet datastructure that uses trees with Path Compression, for a sequence of n make-set operations, and f find-set operations. Theta( f log n / log(1+f/n) ) if f >= n Theta( n + f log n) if f < n For what setting of aprameters is this better and for what it is worse than the linked-list with pointer to front and union by weight method that we discussed earlier. (There we had (m + n log n) where m, the total number of operations can be thought of as n+f, as find-set is called as part of Union). (B) explain why the notion of "rank" defined in class reflects height *prcisely*, when path compression is not applied. [Recall, the rank of the root remain the same if the ranks of the two roots of the trees in the union is differnt, where the smaller-rank root is attached to the higher rank one. If the ranks are the same we attach any of the root to the other and increase the rank.] Why is it hard to maintain the exact height? In general, what can you say about the relation between rank and height? (C) show that the sum of the in-degrees of a directed graph is m, the number of edges. (D) Give an example for graphs which are SPARSE, in trhe sense that m=O(n), and for graphs which are DENSE, in the sense that m=Theta(n^2). For both case you need to supply a graph for every possible n.