CS 6043 – Fall 2024
Homework 2 solutions
1 Problem 1
1.1 Part 1
Consider the input sequence x, x, x, z, z, y, y, y. At the end, we have Cur1 = x, Cur2 = z, and C1 = C2 = 1.
1.2 Part 2a
Say that fy > n/3. Then, Φ will increase by > 2n/3 as a result of all the σi = y (property 4). Since there are < 2n/3 elements other than y, Φ will decrease by at most 2n/3 due to all σi ≠ y (Property 3). Since Φ start at 0, it will thus be positive at the end, so by Property 2, y will indeed be in either Cur1 or Cur2.
1.3 Part 2b
Recall that we are trying to prove the claim about element y with fy > n/3.
Define Φ1: Φ1 = 2C1 if Cur1 = y and Φ1 = −C1 if Cur1 ≠ y.
Define Φ2: Φ2 = 2C2 if Cur1 = y and Φ2 = −C2 if Cur1 ≠ y.
Define Φ = Φ1 + Φ2.
By considering all the cases, it is easy to check that Φ satisfies the desired properties. The most interesting case is when σi ≠ y and one of the Cur contain y; for example, say that Cur1 = y. In this case, Φ1 decreases by 2 but Φ2 increases by 1 (because cur2 ≠ cur1 and so cur2 ≠ y), so overall Φ decreases by 1.
2 Problem 2
no solutions; come to office hours if you want to work it out together.
3 Problem 3
The potential function is as follows. First, for every node v define
ϕ(v) = log(n) − log(# elements in tree containing v)
Then define the potential to be
We clearly have ϕ(v) ≥ 0 for all v, so at all times Φ ≥ 0. We also have Φinit = 0 because at the beginning there are no elements and hence no nodes v. We can thus apply Corollary 1.5 from the lecture notes on amortized analysis.
All that remains is to show that ˆci = O(log(n)) for all operations.
❼ MakeSet(v): here we have ci = 1. Since v enters as a tree of size 1, we have ϕ(v) = log(n), so ∆Φ = log(n), so ˆci = log(n) + 1 = O(log(n)).
❼ Find(v): since we are dealing with the list version, ci = 1, and Φ does not change at all, so ˆci = ci = O(1)
❼ Union(x,y). Say that x ∈ S, y ∈ S
′
, and assume that |S| ≤ |S
′
|. In this case ci = |S|. Note that because |S| ≤ |S
′
| we have |S ∪S
′
| ≥ 2|S|, so for every v ∈ S ϕ(v) decreases by at least 1. Thus ∆Φ ≤ −|S|, so cˆi = ci + ∆Φ ≤ |S| − |S| = 0
4 Problem 4
4.1 Part 1
We will show that ∆ϕ(v) ≤ 0 for every node v, and so ∆Φ < 0. This in turn implies ˆci < ci = 1, which is clearly O(log log(n)).
Let Ty be the tree rooted at ry before the union and let Tx be the tree rooted at rx. Recall that ry becomes the child of rx.
It is easy to see that ϕ(v) remains unchanged for v /∈ Tx ∪ Ty.
For v ∈ Tx, the depth of v remains the same while − log(# of elements in tree containing v) decreases, so ∆ϕ(v) < 0.
Finally, consider v ∈ Ty. Every node in Ty increases its depth by 1, which means that ϕ(v) increases by 1/√log(n). On the other hand, all the nodes in Ty join a new tree which is at least twice as large, so − log(# of elements in tree containing v) decreases by at least 1 (decreases because of the minus sign). So overall ϕ(v) changes by ≤ 1/√log(n) − 1/√log(n) = 0 for every v ∈ Ty.
4.2 Part 2
Say that there k nodes on the path from x to the root, so ci = k. As suggested in the hint, if k < 4√log(n) then ˆci ≤ ci = k = O(√log(n)), so we are done.
So let’s assume that k ≥ 4√log(n). Pet P be path from x to the root (this is the path we do path compression on), and let z be midway note on P; so note that before the Find operation, z has depth k/2 and height ≥ k/2. Thus there are at least k/2 nodes below z on path P, and the depth of each of these nodes decreases by at least k/2 as a result of path compression (for each of these nodes, the depth was > k/2 before path compression and 1 after path compression). Thus, the total decrease in depth of all the nodes below z is ≥ (k/2) · (k/2) = k
/4 and so the potential Φ decreases by at least
Thus we have
cˆi = ci + ∆Φ ≤ ci − k = k − k = 0.
5 Problem 5
5.1 Part 1
Note that bucket the bucket boundaries are 20, 21, 22, 24, 28, 216, 232. In other words, bucket i has upper boundary 22i−1. Thus the last boundary Bi
is the highest i for which
22i−1 ≤ n
Which happens when
2i−1 ≤ log(n)
Which happens when
i ≤ log log(n) + 1
So the total # bucket is O(log log(n)), so just as in class, the # of special edges on a path is O(log log(n) + 1) = O(log log(n)).
EDIT: The analysis above can be improved. Since the maximum rank is actually log(n), the equation we should be using is 22i−1 = log(n), which is true at i = log log log(n). So the number of buckets is actually log log log(n).
I am still giving full credit for a log log(n) solution.
5.2 Part 2
Consider the bucket [B, B2
]. For exactly the same reason as shown in class (and lecture notes), this bucket has at most 2n/2
B elements. Now consider any node x in this bucket. Since rank(parent(x)) everytime x participates in a path compression, in total over all find operations we encounter at most B2 non-special edges from x to parent(x). So the total contribution of this bucket to the total # non-special edges is at most
(Here we are using the fact that for B ≥ 1 we always have 2B ≥ 2B2). Since there are O(log log(n)) buckets, the total contribution of all of them is O(n log log(n))
NOTE: one can actually show that under this bucketing scheme the total # non-special edges encountered is O(n). But O(n log log(n)) is good enough, since that’s what we pay in Part 1.
5.3 Part 3
The amortized update time is O(log log(n)).