Description
Questions:
1. [10 marks] A sorted stack is a stack in which elements are sorted in increasing order
from bottom to top. It supports the following operations:
pop(S), which removes and returns the top element from the sorted stack S.
push(S, x), which first pushes item x onto the top of the sorted stack S and
then maintains the increasing order by repeatedly removing the item immediately
below x until x becomes the largest item in the stack.
Note that here the push operation is different from that of a standard stack. For
example, suppose that the items in the sorted stack S, from bottom to top, are currently
−9, −7, 0, 1, 4, 11, 12, 20. Then, after calling push(S, 5), the content of the stack, from
bottom to top, becomes −9, −7, 0, 1, 4, 5.
We implement the stack as a linked list.
Show that the amortized costs of both operations are O(1).
2. [10 marks] In the vector solution to the problem of maintaining resizable arrays shown
in class, we allocate a new array with twice the size as the old one when inserting into
a full array.
In this question, we study the following alternative solution: Initially the array has
a block of memory that can store at most c0 entries, where c0 is a positive constant.
Each time we insert into a full array, we allocate a new memory block whose size (i.e.,
the maximum number of entries that it could store) is the size of the current memory
block plus a fixed constant value c. We then copy all the elements from the current
memory block to the newly allocated memory block, deallocate the old memory block
and insert the new element into the new block. The new memory block will be used to
store the content of the array afterwards, until we attempt to insert into a full array
again.
Prove that, under this scheme, performing a series of n insertions into an initially
empty resizable array takes Ω(n
2 CSCI 6057/4117
) time, no matter what constant value we assign to c.
3. [15 marks] In class we saw the example of incrementing an initially 0 binary counter.
Now, suppose that the counter is expressed as a base-3 number. That is, it has digits
from {0, 1, 2}.
(i) [5 marks] Write down the pseudocode for INCREMENT for this counter. The running
time should be proportional to the number of digits that this algorithm changes.
(ii) [5 marks] Define the actual cost of INCREMENT to be the exact number of digits
changed during the execution of this algorithm. Let C(n) denote the total cost
of calling INCREMENT n times over an initially 0 base-3 counter. Use amortized
analysis to show that C(n) ≤ (3/2)n for any positive integer n. To simplify your
work, assume that the counter will not overflow during this process.
Note: I will give the potential function as a hint after the problem statement,
though you will learn more if you try to come up with your own potential function.
(iii) [5 marks] Prove that for any c such that C(n) ≤ cn for any positive integer n,
the inequality c ≥ 3/2 holds. Again, assume that the counter will not overflow
during this process.
Hint: Let Di be the counter after the i-th INCREMENT, and Let |Di
|d be the number of
digit d in Di
for d ∈ {0, 1, 2}. Define Φ(Di) = |Di
|1/2 + |Di
|2.
4. [15 marks] In this problem, we consider two stacks, X and Y . n and m denote the
sizes of X and Y (here the size of a stack is the number of elements currently in the
stack), respectively. We maintain these two stacks to support the following operations:
PushX(a): Push element a onto stack X;
PushY(a): Push element a onto stack Y ;
2
MultiPopX(k): pop min(k, n) elements out of stack X;
MultiPopY(k): pop min(k, m) elements out of stack Y ;
Move(k): pop min(k, n) elements out of stack X, and each time an element is
popped, it is pushed onto stack Y .
We represent each stack using a doubly-linked list, so that PushX, PushY, and a single
pop operation on either stack can be performed in O(1) worst-case time.
(i) [6 marks] What is the worst-case running time of MultiPopX(k), MultiPopY(k)
and Move(k)?
(ii) [9 marks] Perform amortized analysis to show that each of these five operations
uses O(1) amortized time.
Hint: Define a potential function that makes use of both n and m. In one possible solution, under the potential function of this method, some operations may
have negative amortized cost. This is however fine. Why? Think about what
conclusion can be drawn when an operation has negative amortized cost with
respect to a particular potential function that starts out at 0 and always remains
nonnegative.
3 CSCI 6057/4117
