Suppose we perform a sequence of stack operations on a stack whose size never exceeds k. After 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.
Amortize cost is two units for every push and two for every pop. Using one unit to pay for the operation and another to keep in the pot. Thus, after every k operations, there are at least k units in the pot. Credit never goes negative, and the amortized complexity is O(n).
Redo Ex 17.1-3 using an accounting method of analysis.
Amortized cost of every operation = 3 units. One unit is used for that operation, one is stored as credit on that element and another one is stored as credit for the 2^i th operation. NOTE : Refer to the dynamic tables for better understanding.
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 O(1), show how to implement a counter as an array of bits so that any sequence of n INCREMENT and RESET operations takes time O(n) on an initially zero counter. (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 RESET in this way, we can limit it to an amount that can be covered by credit from earlier INCREMENTs.
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 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 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 RESET has $1 of credit on it. So the zeroing of bits of A by 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 INCREMENT and $1 for each RESET is sufficient, so the sequence of n INCREMENT and RESET operations takes O(n) time.