Exercise 3 (for week of Mar 8-12)

(A) Explain how to maintin the data feild "SetSize" in a linked-list with 
pointer to front implementation.

(B)Analyze the example of n = m/2 make-set operations followed by 
   union(1,2), union (1,3),..., union(1,n) that was discussed in class, 
   and give a tight asymptotic bound on the running time of a sequence of 
   length m, when
    - we use a linked list with pointer to the front
    - we use a linked list with pointer to the front AND we always append the
 smaller list to the larger list in union operations ("union-by-weight").

(C) Show an example of a sequence of operations of size m that, using the  
 linked list with pointer to the front, and union-by-weight, takes time 
 Theta(m log m)

(D) Consider the DS for Disjoint-set ADt that maintains trees for sets, and in 
which union operations are performed by attaching the tree of the smaller set 
to the tree of the larger set. Show that the height of he obtained trees is 
O(log s)) where s is the size of the tree.