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.