### NAMES:

### LOGINS:

### PRECEPT:

### COS 226 Exercises on Union-Find

*Reference: Chapter 1.5 in Algorithms, 4th edition (Fall 2010 preliminary 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, 0-6, 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 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 E on p. 137.