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.