Problem 3. (15 marks) Once a Push() call is invoked on a full stack (stack.size = stack.capacity), we increase the capacity of a stack (or a queue, or a hash-table) using IncreaseCapacity():

1. Allocate a new array with 2 x stack.capacitycells- ;

2. Copy all items from the original array to the new array, delete the old array.

Analogously to this, once stack.size is small in comparison to stack.capacity, we can decrease the capacity and clear some memory using DecreaseCapacity():

1. Allocate a new array with stack.capacity/2 cells;

2. Copy all items from the original array to the new array, delete the old array.

(Note that both IncreaseCapacity() and DecreaseCapacity() run in \Theta (n)-time .)

a. (5 marks) Prove that invoking DecreaseCapacity() whenever stack.size = stack.capacity/2 is unwise. That is, show that starting with stack.size = 0, there exists a sequence of n Push()/Pop() instructions whose amortized cost is \Omega (n) .

b. (10 marks) Prove that invoking DecreaseCapacity() whenever stack.size = stack.capacity/3 maintains constant amortized cost. That is, show that any sequence of n Push()/Pop() instructions has amortized cost of O(1). You may assume stack.capacity = 1 initially.( Hint: Call an instruction heavy if it invokes either IncreaseCapacity() or DecreaseCapacity(); and call it light otherwise. Light instructions always take O(1). Your argument should probably begin by showing that between any two heavy instructions there have to be at least \small p\cdot m light instructions (by considering all 4 possible cases), where m denotes the capacity of the stack between the two heavy instructions and 0 < p < 1 is a constant you need to find. Then use this claim to prove, by induction, that T(n) defined as the worst-case cost of a sequence of n Push()/PoP() instructions is in O(n).)