NAME:

LOGIN:

PRECEPT:

COS 226 Exercises on Union-Find


1. [Exercise 1.5, revised] Draw the resulting tree after running the quick-union algorithm (Program 1.2) on the sequence:
0-2, 1-4, 2-5, 3-6, 0-4, 6-0, 1-3

Caveat: your tree should be produced exactly as in Program 1.2, so don't interchange the roles of i and j.
















2. Can the following id[] array result when running weighted quick union without path compression? Explain why this is impossible or give a sequence of operations which results in this array.

0 0 1 2 4 4 4 5 3 1 0

Hint: refer to Property 1.3.