### NAMES:

### LOGINS:

### PRECEPT:

### COS 226 Exercises on Union-Find

*Reference: Chapter 1.5 in Algorithms 4th edition (handout)*

**1. **
Draw the resulting tree after running the quick-find algorithm (p. 82)
on the sequence:
0-2, 1-4, 2-5, 3-6, 0-4, 6-0, 1-3

Caution: Make sure that your tree is produced exactly as in the code on
that page, so don't interchange the roles of p and q.

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

i 0 1 2 3 4 5 6 7 8 9
--------------------------
id[i] 1 1 3 1 5 6 1 3 4 5

Hint: Refer to Proposition D on p. 89.