Data Structures, Algorithms, & Applications in Java
Chapter 9, Exercise 9

(a)

We need to (1) add a data member that saves the initial capacity of the list and (2) add code to the pop method so as to halve the size/length of the array stack when the number of elements in this array falls below 25% of its current length. The code for the new class is given below. Most of the needed data members and methods are inherited from the class ArrayStack.

---

public class ArrayStackWithDecreaseCapacity
                           extends ArrayStack
{
   // additional data member
   protected int initialCapacity;       // initial size of stack array

   // constructors
   /** create a stack with initial capacity theInitialCapacity */
   public ArrayStackWithDecreaseCapacity(int theInitialCapacity)
   {
      super(theInitialCapacity);
      initialCapacity = theInitialCapacity;
   }

   /** create a stack with initial capacity 10 */
   public ArrayStackWithDecreaseCapacity()
   {// use default capacity of 10
      this(10);
   }

   /** overrides ArrayStack.pop */
   public Object pop()
   {
      Object x = super.pop();
  
      // decrease size of stack array if occupancy is below 25%
      if (top + 1 < stack.length / 4 && stack.length / 2 >= initialCapacity)
         // halve the size of the array
         stack = ChangeArrayLength.changeLength1D
                       (stack, top + 1, stack.length / 2);

      return x;
   }
}

---

(b)

To obtain the cost of a sequence of stack list operations, we use the cost amortization method in which the sum of the costs of a sequence is determined by first distributing costs from expensive operations to cheaper ones. As an example, consider computing the sum 8 + 10 + 12. The direct way is to add the first two numbers to get 18, and then add in the 12 to get 30. In cost amortization, we alter the numbers, keeping the sum the same. We could shift two units from the 12 to the 8 to get the expression 10 + 10 + 10, which has the same value as the original expression. Following this alteration of the numbers, the sum is more easily computed.

We see that the step count for a sequence of n stack operations is

n + sum of step counts for all invocations of changeLength1D

To compute the step count, we shall amortize the cost of the changeLength1D invocations over the push and pop operations.
When the size of an array is changed from s to 2s, or vice versa, the step count is s.
For every invocation of changeLength1D other than the first, there is a most recent earlier invocation of changeLength1D. The first invocation of changeLength1D increases the size of the array stack from initialCapacity to 2 * initialCapacity and takes initialCapacity steps. These steps may be distributed, at the rate of one step per push operation, to m = initialCapacity of the at least m push operations that must have been done since the start of the operation sequence.

Now consider any other invocation of changeLength1D. If the size of the array stack is increased from s to 2s, then at least s/2 push operations (including the push that triggered the current invocation) must have taken place since the most recent earlier invocation of changeLength1D. The step count for the current invocation is s. We can transfer this count to the push operations that occurred since the most recent earlier invocation of changeLength1D and the current invocation. Each of these push operations is charged at most 2 steps.

If the size of the array stack is decreased from 2s to s, then at least s/2 pop operations (including the pop that triggered the current invocation) must have taken place since the most recent earlier invocation of changeLength1D. The step count for the current invocation is s. We can transfer this count to the pop operations that occurred since the most recent earlier invocation of changeLength1D and the current invocation. Each of these pop operations is charged at most 2 steps.

The amortization scheme just described transfers the cost of the changeLength1D invocations to some of the push and pop operations that have occurred. No push/pop is charged more than 2 steps. Since the number of push and pop operations is at most n, the total cost transferred to the insert and remove operations is at most 2n. Consequently, the cost of the n list operations is at most n + 2n = 3n. Therefore, the time taken by any sequence of n stack operations is O(n).