CompSci 261, Winter 2018, Homework 1

  1. The dynamic array data structure described in the lectures maintains a block $B$ of memory and a number $L$, the length of the dynamic array. In the lectures, we analyzed it with the potential function $\Phi=|2L-\operatorname{sizeof}(B)|$, using an absolute value operation to make sure that the potential function stays non-negative. Instead, in this question, we will make the function non-negative a different way, by choosing $\Phi=\max(0,2L-\operatorname{sizeof}(B))$.

    1. Would this change of potential function affect the analysis of grow operations that replace $B$ by a larger block? Why or why not?

    2. Recall that the shrink operation described in class only decreases $L$ by one, without ever replacing $B$. If the new potential function has the value $x$ before a shrink operation, what possible values (as a function of $x$) could the potential function have after the operation?

    3. Suppose that we use a shrink operation that replaces $B$ by a shorter block, of length exactly $2L$, whenever $L\lt\operatorname{sizeof}(B)/4$. We saw in class that, with the original potential function, this operation takes constant amortized time. Would it still have constant amortized time with the new potential function? Explain why or why not.

  2. The dynamic arrays described in class (and as implemented in Python) cannot efficiently remove an item $A[i]$ from the middle of an array $A$. Instead, performing this operation while preserving the order of the remaining items requires time proportional to the length of the array to move each element in a position greater than $i$ one position earlier in the array. But suppose that we do not care whether the remaining items stay in the same order, as long as the array contains the same remaining items in some order. In this case, describe how to remove $A[i]$ from an array, using only a constant number of get, set, grow, or shrink operations.

  3. Your friend, a bad computer programmer, has implemented a stack data structure badly, so that its pop operation takes $O(n)$ time to perform, when there are $n$ items in the stack. However, your friend's stack implementation only takes $O(1)$ time per push, and it works correctly: it produces the same results as a dynamic array based stack would produce, but takes more time to do it. Describe a potential function $\Phi$ such that, with your potential function, the times for the two operations of your friend's stack are reversed: it takes $O(1)$ amortized time per pop and $O(n)$ amortized time per push.

    (Hint: Choose your function to grow quickly as a function of $n$, so that it shrinks quickly on each pop and cancels the actual time of the pop. How quickly can you make it grow while still having only $O(n)$ time per push?)

  4. In class we studied a binary counter, for which the times per operation had the sequence $$1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,\dots,$$ and we showed that the average time per operation was $O(1)$, both by using the potential function method and by averaging these numbers directly. In this sequence, the number at position $i$ (starting from $i=1$) is just one plus the number of zeros in the low-order positions of the binary representation of $i$. Suppose instead that we have a new data structure whose times per operation are $$1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,1,2,1,4,1,2,1,8,\dots,$$ where each number $x$ in the first sequence is replaced by $2^{x-1}$. By averaging these numbers directly, give an accurate bound in $O$-notation for the average time per operation of this new data structure, as a function of the total number $n$ of operations performed.

    (Hint: compute the average by summing the copies of each power of two separately. Among the first $n$ operations, how many copies of each power of two are there? How many different powers of two are there?)