CS 6043 – Fall 2024
Homework 1 solutions
1 Problem 1
All digits are now 0 . . . d - 1. As in class, observe that every increment causes some number of (d - 1)-to-0 flips, as well as exactly one additional flip.
Set
Φ = # non-zero bits in counter
We then have
ci = 1 + # (d-1)-to-zero flips
And
Φi - Φ(i - 1) ≤ 1 - # (d-1)-to-zero flips
So then
ˆ(c)i = ci + Φi - Φ(i - 1) ≤ 2
So in fact, no matter the value of d, the amortized number of flips is at most d = O(1). (The constant inside O(1) actuallys down with d, but O(1) is good enough.)
2 Problem 2
Say that at some point we have T.num = x, T.size = 4x for some large x, and then operation i is a T.pop. In this case we do a rebuild, so after the rebuild we have T.num = x - 1 and T.size = 2T.num = 2(x - 1)
ci = x
and
Φi-1 = 0
and
Φi = 4(x - 1) - 2(x - 1) = 2(x - 1)
So
ˆ(c)i = x + 2(x - 1) = 3x - 1,
which is very large when x is big, so this potential function does not work.
3 Problem 3
3.1 Part 1
Recall that if we do n increments then the number of bits used is Blog(n)...B0 . Recall that bit i is flipped n/2i times. Using aggregate analysis, we now have that the total time over n increments is
3.2 Part 2
Intuitively, for the accounting analysis, we want to add i$ to bit Bi if that bit is a 1, so that this money can be used to pay for flipping bit Bi. In fact to make the algebra work out we need to add 2i$ to bit Bi. Recall that Bi is always one or zero.
To capture the above intuition, we use the following potential function:
Recall that every increment finds the right 0-bit (say Bk ) and then flips Bk to 1 while flipping all of B0 . . . Bk-1 to 0.
Let’s focus on some increment j and let Bk be the right-most 0-bit right before the increment. This means that we end up flipping all of B0 . . . Bk so we have: We have:
and
where in both of the above equations we are using the standard summation
formula We thus have
Multiplying out all the parentheses gives us
ˆ(c)j = — .5k2 + 4.5k — 2
We thus have ˆ(c)j = f(k) for the function f(k) = — .5k2 + 4.5k — 2.
Since .5k2 grows asymptotically faster than 4.5k, the function f(k) is upper bounded by a constant. More concretely, is not hard to show that f(k) ≤ 9 for k ≥ 0. You can this either using basic caluclus to optimize the function (it is maximum when k = 4.5), or you can simply plot the function on a graphing calculator.
In other words, we always have ˆ(c)j ≤ 9 = O(1), so the amortized cost per flip is O(1).
4 Problem 4
Algorithm:
● Whenever T.num = T.size: rebuild into new array of size T.size = 1.3 · T.num
● Whenever T.num ≤ T.size/1.5: rebuild into new arrayof size T.size = 1.3 · T.num
Use potential function
Φ(D) = 10 · |1.3T.num — T.size|
Analysis
● If no rebuild then ci = 1 and Φ(Di )—Φ(Di-1 ) is at most 10·1.3 = O(1), so ˆ(c)i = O(1).
● note that AFTER every rebuild we have Φ(D) = 0, because rebuild always sets T.size = 1.3T.num after
● If append causes rebuild then:
– ci = T.num + O(1)
– Φ(Di ) — Φ(Di-1 ) = 0 — 10 · .3T.num = —3T.num
— So ˆ(c)i = O(1) + T.num — 3T.num < O(1).
● If pop causes rebuild then:
— ci = T.num + O(1)
— Φ(Di ) — Φ(Di-1 ) = 0 — 10 · .2T.num = —2T.num
5 Problem 5
Let Si be the number of balls in bin i. We then set
, where | · | is the absolute value function.
Consider any move step from some bin Bj to some other bin Bk . As mentioned in the hint, before the move we have Sj > n and Sk < n, so it is easy to see that every move decreases Φ by exactly 2.
On the other hand, it is easy to check that
Φfinal = 0
Finally, since |Si — n| ≤ Si + n, we have
. Thus, the total number of moves is at most 2n2 /2 = n2 , as desired.