NAMES:

LOGINS:

PRECEPTS:

COS 226 Exercises on Union-Find


Reference: Section 1.5 in Algorithms 4/e.


1. Give the id[] array and draw the corresponding forest-of-trees representation that results from the following sequence of union operations using the quick-union algorithm described starting on p. 224: 
0-2, 1-4, 2-5, 3-6, 0-4, 0-6, 1-3

Assume that N equals 7. Warning: Make sure that your id[] array is produced exactly as in the code on p. 224—do not interchange the roles of p and q.
















2. Draw the forest-of-trees representation of the following id[] array. 

  i    0 1 2 3 4 5 6 7 8 9 
--------------------------
id[i]  1 1 3 1 5 6 1 4 3 5
Can this be the result of running the weighted quick union algorithm (without path compression)? Either give a sequence of union operations that results in this array or explain why no such sequence exists.

Hint: Refer to the proof of Proposition H on p. 229.