Homework 1 - Dualing Stacks and Objects with Python

Introduction

Recall the stack data structure which you probably learned about in CS 240. Stacks support LIFO (last in, first out) operations via push and pop operations. Amortized analysis provides insight into the most efficient ways to do certain expensive manipulations, and specifies when we can spread their cost over a set of operations. For example, if we are using a dynamic array to store data, and we need to expand it when it gets full or shrink it when parts of it are not in use, when and how much should we grow or shrink the array? Amortized analysis answers these questions.

In this assignment you will implement a data structure that grows or shrinks at times and in amounts based on amortized analysis. In particular, suppose we need two stacks that are related in such a way that usually one is large when the other is small. To make the most efficient use of space, we can have an array/list in which we store both of them, with each having its bottom at one end of the array/list. In this way, the stacks grow toward one another, sharing the space in the array/list.

Of course, it might happen that the stacks grow together to the point that they use up all the space in the array/list. In this case, we need to expand the array. How much? If we were to expand the array by just one slot (the minimum necessary), then a sequence of push operations on a full array would incur copying all the elements in the full array into a new array, as well as the single copy operation needed to add the new value to a stack. In this case, each push operation when the underlying array is full would each require O(n) data copy operations, where n is the size of the array, which is rather expensive.

However, if we increase the size of the array by a factor of k, so that an array of size n is replaced by an array of size kn, then there will be n + 1 data copy operations when the array grows (n to copy the existing data and 1 more for the new element), followed (in the worst case) by (k −1)n operations for all the (k −1)n pushes that can be done before the array becomes full again. The average cost of a push between expansions is therefore $$((n + 1) + (k −1)n)/(k −1)n = (kn + 1)/(kn −n) \in \mathcal{O}(1)$$. So it is more efficient to expand the array by a constant factor k. What should k be? The bigger k is, the lower the amortized cost, but we are also trying to save space. Generally a factor of 2 is used. So we double the size of the array when it is expanded. A similar analysis shows that if we want to minimize space usage without incurring excessive costs when shrinking the array, we should shrink the array when the it gets to be half full.