In class we explored a bit of the theory behind resizing arrays. While our discussion was motivated by the C$++$ implementation of the vector, and though we discussed it in the context of ADT Stack, the ideas contained in the analysis are powerful and worth understanding deeply and more generally. They apply to any structure implemented using blocks of contiguous memory, and they also serve as a perfect application of a new analysis tool that you'll use in CPSC$320$: Amortized Analysis.

In this question we examine the problem of array resizing from a slightly different perspective, and we use that new approach to devise a resizing policy that we can use for resizing downward, as well as upward. In the end, we generalize our discoveries so we understand the class of policies that will give us the same asymptotic results.

The resizing problem is$,$ fundamentally, an analysis of the trade$-$off between the cost of computation, and the space used by a structure. In this problem, we wish to bound both of these features by some constant factor of the number of operations performed $($additions and removals$)$ over the lifetime of the structure.