We start by reviewing the results that we explored in class. Consider a sequence of additions to an array, beginning with an empty array of capacity 1 . Suppose that our growth resize policy is as follows: When the array overfills, 1. Create a new array whose capacity is twice the original. 2. Copy all existing data into the new array. 3. Free the space associated with the old array. 4. Rename the new array, using the old name. After the resize, we add the new data element to the array. Note that the copy step requires n copies where n is the amount of data the array contains before the addition. We can describe the policy more succinctly as: "if n+1>c update c to 2c " where c is the capacity of the array. The criteria for resizing is that the array becomes overfull (n+1>c) and the action is to double the capacity (c=2c). How many times is the array resized for a sequence of 351192 additions? Now suppose that there are 348248 consecutive removals from the structure. How much unused capacity exists in the array? (cells) That's a waste of memory! In response, we develop a policy for resizing downward