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.capacity cells; 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 increas eCapacity() and DecreaseCapacity() run in ?(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 S2(n) b. (10 marks) Prove that invoking DecreaseCapacity() whenever stack, size = stackcapacity/3 main- tains constant amortized cost. That is, show that any sequence of n PushO/Pop) instructions has amortized cost of O(1). You may assume stack.capacity1 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 p m light instructions (by considering all 4 possible cases), where m denotes the capacity of the stack between the two heavy instructions and 0