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.