Union-Find
Assignment 1
Submit your answers via Moodle. Submissions may be uploaded as PDF or as plain text files.
A LaTeX answer template is available here: answers.tex.
New to LaTeX? See the LaTeX guide for DSA students.
Exercise 1: Analysis of quick-find (8 points)
Show the contents of the id[] array and the number of times the array is accessed
for each input pair when you use quick-find (slide 35) for the sequence
(9,0) (3,4) (5,8) (7,2) (2,1) (5,7) (0,3) (4,2).
In your submission, document each union step in a table with columns 0 to 9,
showing the contents of id[] before and after the operation as well as the number of array accesses.
Exercise 2: Analysis of quick-union (8 points)
Repeat Exercise 1, but use quick-union (slide 73).
In addition, draw the tree structures represented by the id[] array
after each input pair is processed.
Exercise 3: union() implementation (4 points)
Give a counterexample that shows why this intuitive implementation of
union() for quick-find is not correct:
def union(self, p, q):
if self.connected(p, q):
return
for i in range(len(self.id)):
if self.id[i] == self.id[p]:
self.id[i] = self.id[q]Exercise 4: Weighted quick union (4 points)
Explain which of these id[] arrays cannot occur during the execution of the
weighted quick union algorithm.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| A. | a[i] |
8 | 0 | 4 | 0 | 0 | 4 | 0 | 4 | 2 | 0 |
| B. | a[i] |
4 | 1 | 8 | 2 | 1 | 5 | 1 | 1 | 4 | 5 |
| C. | a[i] |
3 | 3 | 6 | 9 | 3 | 6 | 3 | 4 | 1 | 9 |
| D. | a[i] |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 7 |