17.2 The accounting method

17.2-1

Suppose we perform a sequence of stack operations on a stack whose size never exceeds $k$. After every $k$ operations, we make a copy of the entire stack for backup purposes. Show that the cost of $n$ stack operations, including copying the stack, is $O(n)$ by assigning suitable amortized costs to the various stack operations.

[We assume that the only way in which COPY is invoked is automatically, after every sequence of $k$ PUSH and POP operations.]

Charge $\$2$for each$\text{PUSH}$and$\text{POP}$operation and$\$0$ for each $\text{COPY}$. When we call $\text{PUSH}$, we use $\$1$to pay for the operation, and we store the other$\$1$ on the item pushed. When we call $\text{POP}$, we again use $\$1$to pay for the operation, and we store the other$\$1$ in the stack itself. Because the stack size never exceeds $k$, the actual cost of a $\text{COPY}$ operation is at most $\$k$, which is paid by the$\$k$ found in the items in the stack and the stack itself. Since $k$ $\text{PUSH}$ and $\text{POP}$ operations occur between two consecutive $\text{COPY}$ operations, $k$ of credit stored, either on individual items (from $\text{PUSH}$ operations) or in the stack itself (from $\text{POP}$ operations) by the time a $\text{COPY}$ occurs. Since the amortized cost of each operation is $O(1)$ and the amount of credit never goes negative, the total cost of $n$ operations is $O(n)$.

17.2-2

Redo Exercise 17.1-3 using an accounting method of analysis.

Let $c_i =$ csot of $i$th operation.

$$c_i = \begin{cases} i & \text{if i is an exact power of 2}, \\ 1 & \text{otherwise}. \end{cases}$$

Charge each operation $3$ (amotized cost $\hat c_i$).

• If $i$ is not an exact power of $2$, pay $\$1$, and store$\$2$ as credit.
• If $i$ is an exact power of $2$, pay $\$i$, using stored credit. $$\begin{array}{cccc} \text{Operation} & \text{Cost} & \text{Actual cost} & \text{Credit remaining} \\ \hline 1 & 3 & 1 & 2 \\ 2 & 3 & 2 & 3 \\ 3 & 3 & 1 & 5 \\ 4 & 3 & 4 & 4 \\ 5 & 3 & 1 & 6 \\ 6 & 3 & 1 & 8 \\ 7 & 3 & 1 & 10 \\ 8 & 3 & 8 & 5 \\ 9 & 3 & 1 & 7 \\ 10 & 3 & 1 & 9 \\ \vdots & \vdots & \vdots & \vdots \end{array}$$ Since the amortized cost is$\$3$ per operation, $\sum\limits_{i = 1}^n \hat c_i = 3n$.

We know from Exercise 17.1-3 that $\sum\limits_{i = 1}^n \hat c_i < 3n$.

Then we have

$$\sum_{i = 1}^n \hat c_i \ge \sum_{i = 1}^n c_i \Rightarrow \text{credit} = \text{amortized cose} - \text{actual cost} \ge 0.$$

Since the amortized cost of each operation is $O(1)$, and the amount of credit never goes negative, the total cost of $n$ operations is $O(n)$.

17.2-3

Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it $0$). Counting the time to examine or modify a bit as $\Theta(1)$, show how to implement a counter as an array of bits so that any sequence of $n$ $\text{INCREMENT}$ and $\text{RESET}$ operations takes time $O(n)$ on an initially zero counter. ($\textit{Hint:}$ Keep a pointer to the high-order $1$.)

We introduce a new field $A.max$ to hold the index of the high-order $1$ in $A$. Initially, $A.max$ is set to $-1$, since the low-order bit of $A$ is at index $0$, and there are initially no $1$'s in $A$. The value of $A.max$ is updated as appropriate when the counter is incremented or reset, and we use this value to limit how much of $A$ must be looked at to reset it. By controlling the cost of $\text{RESET}$ in this way, we can limit it to an amount that can be covered by credit from earlier $\text{INCREMENT}$s.

  1 2 3 4 5 6 7 8 9 10 11 INCREMENT(A) i = 0 while i < A.length and A[i] == 1 A[i] = 0 i = i + 1 if i < A.length A[i] = 1 // Additions to book's INCREMENT start here. if i > A.max A.max = i else A.max = -1 
 1 2 3 4 RESET(A) for i = 0 to A.max A[i] = 0 A.max = -1 

As for the counter in the book, we assume that it costs $\$1$to flip a bit. In addition, we assume it costs$\$1$ to update $A.max$.

Setting and resetting of bits by $\text{INCREMENT}$ will work exactly as for the original counter in the book: $\$1$will pay to set one bit to$1$;$\$1$ will be placed on the bit that is set to $1$ as credit; the credit on each $1$ bit will pay to reset the bit during incrementing.

In addition, we'll use $\$1$to pay to update$max$, and if$max$increases, we'll place an additional$\$1$ of credit on the new high-order $1$. (If $max$ doesn't increase, we can just waste that $\$1$—it won't be needed.) Since$\text{RESET}$manipulates bits at positions only up to$A.max$, and since each bit up to there must have become the high-order$1$at some time before the high-order$1$got up to$A.max$, every bit seen by$\text{RESET}$has$\$1$ of credit on it. So the zeroing of bits of $A$ by $\text{RESET}$ can be completely paid for by the credit stored on the bits. We just need $\$1$to pay for resetting$max$. Thus charging$\$4$ for each $\text{INCREMENT}$ and $\$1$for each$\text{RESET}$is sufficient, so the sequence of$n\text{INCREMENT}$and$\text{RESET}$operations takes$O(n)\$ time.