CSE 5311 Section 501 Fall 1998
Homework 4
Due: March 25, 1998, in class
Let represent the cost of the ith Insert. The value of
is
i if i is an exact power of 3, 1 otherwise. By the aggregate method, the
cost T(n) of performing n operations is
The first term represents the powers of 3
from 1 to n, each with cost
. The remaining terms represent the
operations 1 to n minus the powers of three, each with cost 1.
Simpifying,
Thus, the amortized cost of each operation is O(n)/n = O(1).
Our goal here is to define a potential function that is nonnegative
and can be used to show the desired bounds on the amortized cost of each
operation (in this case O(1)). Let the potential function be:
The first term represents the potential left behind after each operation, and the second term represents the potential lost due to the power-of-3 operations. Expanding the summation, we get
Letting , we need to show that
for all i
> 0. There are two cases. Case I is when i is a power of 3, i.e.,
, where a is a nonnegative integer. The potential function is
Case II is when i is not a power of 3, i.e., for
some nonnegative integer a. Let
, where integer b > 0.
The potential function is
Since for all i,
is
an upper bound on the actual cost of the n operations. So now we must
find an expression for
. Again, there are two cases. Case I is
when i is a power of 3, i.e.,
, for some nonnegative integer
a. For this case, the amortized cost is
Case II is when i is not a power of 3. The amortized cost is
Since the amortized cost is constant in both cases, the upper
bound on the actual cost of n operations
, and the amortized cost per operation is then O(1).
Using the accounting method, we want to assign a cost to the
non-power-of-3 operations that is enough of an overestimate that
sufficient credit builds up to cover the cost of the power-of-3
operations. Let the amortized cost of each operation be
To show that the credit in the data structure never becomes negative, we
show by induction that there is always 1/2 credit remaining after , because the credit only increases for non-powers-of-3 by 3/2.
Basis: . Use one credit for actual cost, 1/2 credit left
behind.
Assume: Credit remaining after operation is 1/2.
Induction: Credit remaining after operation is 1/2.
Proof: Cost of this last operation is . The credit available to
pay for the cost consists of 1/2 credit remaining from the
operation, plus 5/2 - 1 = 3/2 credits for each non-power-of-3
operation between
and
, plus 3/2 credits allotted for
this operation. Since there are
operations between
and
, then the total credit available to perform the
operation is
Therefore, after using the credits to pay for the operation, we
still have 1/2 credit remaining. Thus, the credit is never negative.
Since the amortized costs for both operations are constants, we have O(n) performance for n operations, and O(1) for each individual operation.
* Insert 12 H1: 12 * Insert 7 H1: 7 | 12 * Insert 25 H1: 7 /| / | 12 25 * Insert 15 H1: 7 /| / | 15 12 | | 25 * Insert 28 H1: 7 /|\ / | \ 15 12 28 | | 25 * Insert 33 H1: 7 /|\ / | \ 15 12 28 | | | | 25 33 * Insert 41 H1: 7 /|\ / | \ 15 12 28 | |\ | | \ 25 33 41
* Insert 18 H2: 18 * Insert 3 H2: 3 | 18 * Insert 37 H2: 3 /| / | 18 37 * Insert 6 H2: 3 /| / | 6 18 | | 37
___3___ / / \ \ / / \ \ 7 6 18 28 /| | |\ / | | | \ 15 12 37 33 41 | | 25
___6___ / / \ \ / / \ \ 7 28 37 18 /| | | / | | | 15 12 33 41 | | 25
min(H) +---------------------|-----+ | v | H1: +-41--33--28--15--25--7--12-+
min(H) +--------|-----+ | v | H2: +-6--37--3--18-+
min(H) +--------|--------------------------------+ | v | +-6--37--3--18--41--33--28--15--25--7--12-+
min(H) +--------|--------------------------------+ | v | +-6--37--3--18--41--33--28--15--25--7--12-+ min(H) +--------|-----------------------------+ | v | +-6--37--18--41--33--28--15--25--7--12-+ min(H) +--------|-------------------------+ | v | +-6--37--18--33--28--15--25--7--12-+ | | 41 min(H) +--------|---------------------+ | v | +-6--37--18--28--15--25--7--12-+ | | | | 41 33 min(H) +--------|-----------------+ | v | +-6--37--18--15--25--7--12-+ / \ / \ 28 41 | | 33 min(H) +--------|---------------+ | v | +-6--37--18----15--7--12-+ / \ | / \ | 28 41 25 | | 33 min(H) +--------|-----------+ | v | +-6--37--18----15--7-+ / \ | | / \ | | 28 41 25 12 | | 33 min(H) +--------|-----------+ | v | +-6--37--18------ 7--+ / \ /\ / \ / \ 28 41 15 12 | | | | 33 25 min(H) +--------|----+ | v | +-6--37--7----+ /|\ / | \ 18 15 12 /| | / | | 28 41 25 | | 33 min(H) +-------|----+ | v | +-6-----7----+ | /|\ | / | \ 37 18 15 12 /| | / | | 28 41 25 | | 33 min(H) +-|----------+ | v | +-6-----7----+ | /|\ | / | \ 37 18 15 12 /| | / | | 28 41 25 | | 33
Once you have successfully compiled and executed your program on omega, send the code to cs5311-turnin@cse. The source code must be submitted by 5:30 p.m. on the due date. In addition to identifying yourself and the homework number in a comment at the top of your code, also include a ``Compile Using'' comment line so we know how to compile your program. Be sure to use good programming and documentation style.