CS 61B Disjoint Sets and Asymptotics
Spring 2021
1 Disjoint Sets, a.k.a. Union Find
Discussion 6: February 22, 2021
In lecture, we discussed the Disjoint Sets ADT. Some authors call this the Union Find ADT. Today, we will use union find terminology so that you have seen both.
(a) What are the last two improvements (out of four) that we made to our naive implementation of the Union Find ADT during lecture 14 (Monday’s lecture)?
1. Improvement 1:
2. Improvement 2:
(b) Assume we have nine items, represented by integers 0 through 8. All items are initially uncon- nected to each other. Draw the union find tree, draw its array representation after the series of connect() and find() operations, and write down the result of find() operations using Weight- edQuickUnion without path compression. Break ties by choosing the smaller integer to be the root.
Note: find(x) returns the root of the tree for item x.
connect(2, 3);
connect(1, 2);
connect(5, 7);
connect(8, 4);
connect(7, 2);
find(3);
connect(0, 6);
connect(6, 4);
connect(6, 3);
find(8);
find(6);
(c) Extra: Repeat the above part, using WeightedQuickUnion with Path Compression.
(d) What is the runtime for ”connect” and ”isConnected” operations using our Quick Find, Quick Union, and Weighted Quick Union ADTs? Can you explain why the Weighted Quick union has better runtimes for these operations than the regular Quick Union?
2 Disjoint Sets and Asymptotics 2 Asymptotics
(a)
(b)
Order the following big-O runtimes from smallest to largest.
O(log n), O(1), O(nn), O(n3), O(n log n), O(n), O(n!), O(2n), O(n2 log n)
Are the statements in the right column true or false? If false, correct the asymptotic notation (Ω(·), Θ(·), O(·)). Be sure to give the tightest bound. Ω(·) is the opposite of O(·), i.e. f(n) ∈ Ω(g(n)) ⇐⇒ g(n) ∈ O(f(n)).
Hint: Make sure to simplify the runtimes first.
(c)
Give the worst case and best case runtime in terms of M and N. Assume ping is in Θ(1) and returns an int.
if (ping(i, j) > 64) break;
i) f(n) = 20501
ii) f(n) = n2 + n
iii) f(n) = 22n + 1000
iv) f(n) = log(n100)
v) f (n) = n log n + 3n + n vi) f (n) = n log n + n2 vii) f (n) = n log n
g(n) = 1
g(n) = 0.000001n3 g(n) = 4n + n100
g(n) = nlogn g(n)=n2 +n+logn g(n) = log n + n2 g(n) = (log n)2
f (n) ∈ f (n) ∈ f (n) ∈ f (n) ∈ f (n) ∈ f (n) ∈ f (n) ∈
O(g(n)) Ω(g(n)) O(g(n)) Θ(g(n)) Ω(g(n)) Θ(g(n)) O(g(n))
i) True, this an accurate tightest bound. ii) True, this an accurate tightest bound. iii) True, this an accurate tightest bound. iv) True, this an accurate tightest bound. v) True, this an accurate tightest bound. vi) True, this an accurate tightest bound. vii) True, this an accurate tightest bound.
False, an accurate tightest bound would be False, an accurate tightest bound would be
False, an accurate tightest bound would be
False, an accurate tightest bound would be False, an accurate tightest bound would be
False, an accurate tightest bound would be False, an accurate tightest bound would be
for (int i = N; i > 0; i–) {
for (int j = 0; j <= M; j++) {
1
2
3 4} 5}
Disjoint Sets and Asymptotics 3 (d) Below we have a function that returns true if every int has a duplicate in the array, and false if
10 11 12 13 14
there is any unique int in the array. Assume sort(array) is in Θ(N log N ) and returns sorted.
public static boolean noUniques(int[] array) { array = sort(array);
int N = array.length;
for (int i = 0; i < N; i += 1) {
boolean hasDuplicate = false; for (int j = 0; j < N; j += 1) {
if (i != j && array[i] == array[j]) { hasDuplicate = true;
}
if (!hasDuplicate) return false; }
return true; }
1. Give the worst case and best case runtime where N = array.length.
array
1
2
3
4
5
6
7
8 9}
2. Try to come up with a way to implement noUniques() that runs in Θ(NlogN) time. Can we get any faster?