NAMES:

LOGINS:

PRECEPT:

COS 226 Exercises on Union-Find


Reference: Chapter 1.5 in Algorithms, 4th edition.


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 on p. 132: 
0-2, 1-4, 2-5, 3-6, 0-4, 6-0, 1-3

Warning: Make sure that your id[] array is produced exactly as in the code on p. 132 (so, don't 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 3 4 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 E on p. 137.