NAME:

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














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