## Description

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

) 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