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.