| CSC300: HW Answers [3/4] | |
1.5.1: 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 for the sequence 9-0 3-4 5-8
7-2 2-1 5-7 0-3 4-2.
You can check your answer in TestUF.java.
Uncomment the correct line in getUF to return the correct type of UF.
Put the following in main:
show(10, "9 0, 3 4, 5 8, 7 2, 2 1, 5 7, 0 3, 4 2");
After running you should see pictures in Desktop/GraphvizOutput
For this problem I get:
10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9 0: 9[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]
3 4: 8[0, 1, 2, 4, 4, 5, 6, 7, 8, 0]
5 8: 7[0, 1, 2, 4, 4, 8, 6, 7, 8, 0]
7 2: 6[0, 1, 2, 4, 4, 8, 6, 2, 8, 0]
2 1: 5[0, 1, 1, 4, 4, 8, 6, 1, 8, 0]
5 7: 4[0, 1, 1, 4, 4, 1, 6, 1, 1, 0]
0 3: 3[4, 1, 1, 4, 4, 1, 6, 1, 1, 4]
4 2: 2[1, 1, 1, 1, 1, 1, 6, 1, 1, 1]
1.5.2: Do Exercise 1.5.1, but use quick-union (page
224). In addition, draw the forest of trees represented by the
id[] array after each input pair is
processed.
10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9 0: 9[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]
3 4: 8[0, 1, 2, 4, 4, 5, 6, 7, 8, 0]
5 8: 7[0, 1, 2, 4, 4, 8, 6, 7, 8, 0]
7 2: 6[0, 1, 2, 4, 4, 8, 6, 2, 8, 0]
2 1: 5[0, 1, 1, 4, 4, 8, 6, 2, 8, 0]
5 7: 4[0, 1, 1, 4, 4, 8, 6, 2, 1, 0]
0 3: 3[4, 1, 1, 4, 4, 8, 6, 2, 1, 0]
4 2: 2[4, 1, 1, 4, 1, 8, 6, 2, 1, 0]
1.5.3: Do Exercise 1.5.1, but use weighted quick-union (page 228).
10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9 0: 9[9, 1, 2, 3, 4, 5, 6, 7, 8, 9]
3 4: 8[9, 1, 2, 3, 3, 5, 6, 7, 8, 9]
5 8: 7[9, 1, 2, 3, 3, 5, 6, 7, 5, 9]
7 2: 6[9, 1, 7, 3, 3, 5, 6, 7, 5, 9]
2 1: 5[9, 7, 7, 3, 3, 5, 6, 7, 5, 9]
5 7: 4[9, 7, 7, 3, 3, 7, 6, 7, 5, 9]
0 3: 3[9, 7, 7, 9, 3, 7, 6, 7, 5, 9]
4 2: 2[9, 7, 7, 9, 3, 7, 6, 7, 5, 7]
1.5.8: Give a counterexample that shows why this intuitive implementation of union() for quick-find is not correct:
01 |
public void union(int p, int q) { if (id[p] == id[q]) return; // Rename p's component to q's name. for (int i = 0; i < id.length; i++) if (id[i] == id[p]) id[i] = id[q]; count--; } |
Here's an example:
show(3, "1 0, 0 2");
Correct answer:
3[0, 1, 2]
1 0: 2[0, 0, 2]
0 2: 1[2, 2, 2]
With the broken code above:
3[0, 1, 2]
1 0: 2[0, 0, 2]
0 2: 1[2, 0, 2]
The problem is that id[p] is changes!
To correct this, it is sufficient to use:
int pid = id[p];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = id[q];
The book also uses a variable for qid.
But this change does not affect correctness, since id[q] does not change.
1.5.10: In the weighted quick-union algorithm, suppose that we
set id[find(p)] to q instead of to
id[find(q)]. Would the resulting algorithm be correct?
Yes, the algorithm would be correct. However, it would be increase the tree
height, so the performance guarantee would be invalid. As an example,
Suppose we have three elements that we union together.
Then weighted union should not produce a tree of depth 2.
Here is the correct alorgithm:
3[0, 1, 2]
0 1: 2[0, 0, 2]
1 2: 1[0, 0, 0]
The final forest looks like this:
0
/ \
1 2
It is depth 1.
Here is the badly performing version:
3[0, 1, 2]
0 1: 2[0, 0, 2]
1 2: 1[0, 0, 1]
The final forest looks like this:
0
\
1
\
2
It has depth 2.
Here is the code for the badly performing version:
01 |
public void union(int p, int q) { int pid = find(p); int qid = find(q); if (pid == qid) return; if (sz[pid] < sz[qid]) { id[pid] = q; // should be qid, not q. sz[qid] += sz[pid]; } else { id[qid] = p; // should be pid, not p. sz[pid] += sz[qid]; } count--; } |