1
$\begingroup$

I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation.

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ because for example going from 100 to 101 would set $\max[A]$ to $-1$ which does not make much sense.

Then, "if max[A] increases place 1 dollar as a credit on a new high-order 1." - when the high-order 1 has been set, 2 coins were given for this operation in increment - one for actually setting the bit to 1 and one for for the future, hence eventual reset to 0 would be covered by it. Why do we need to put yet another coin?

$\endgroup$
1
  • $\begingroup$ What have you tried? It sounds like you're asking "If I modified the argument as follows, would the proof still go through?" So, have you tried modifying the argument as you propose (to avoid putting another coin), and checking whether all of the subsequent reasoning still goes through or not? That would be a reasonable way to approach this. To help us help you, we ask you to make a serious effort on your own before asking, and to show us in the question what you've tried. $\endgroup$
    – D.W.
    Commented Jun 5, 2015 at 0:58

1 Answer 1

2
$\begingroup$

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ does not make much sense.

It does not make sense because it is wrong. This part of code has been wrongly aligned. It should be

5. if i < length [A]
6.   then A[i] = 1
7.       if i > max[A]
8.         then max[A] = i
9.   else max[A] = -1 // the array A overflows; A is effectively reset to 0. So max[A] = -1.

Why do we need to put yet another coin?

As explained in the article, the amortized costs of INC and RESET are $\$$4 and $\$$1, respectively.

  • $\$$4 for INC is composed of

    • pay $\$$1 to set 0 to 1;
    • place another $\$$1 on the same bit as credit. The credit on each 1 bit will pay to reset the bit during INC (not by RESET);
    • pay $\$$1 to update max[A]
    • place an additional $\$$1 of credit on the new high-order 1 (If max[A] does not increase we just waste that one dollar). The credit will pay to reset the bit during RESET.
  • $\$$1 for RESET is

    • pay $\$$1 to reset max[A]. Note that the resetting of bits From i = 0 to max[A] is paid for by the credit stored on the bits (each bit reset here has a credit on it due to the last $\$$1 for INC).

Added: For your specific question on "another $\$$1 on bit 1", note that the first $\$$1 credit on each bit 1 put by INC is consumed by the "resetting" part in INC itself (just as in the binary counter without the RESET operation). That is why you need another $\$$1 on each, to pay for the RESET operation (i.e., the code From i = 0 to max[A] A[i] = 0). The charged $\$$1 for RESET operation is only for the update of max[A].

$\endgroup$
4
  • $\begingroup$ Yes, but my second question was specifically about the last dollar for the INC operation. We already put $\$$1 to set every 0 to 1 (first dollar), but then for some reason we put another $\$$ 1 for the high order 1, even though there is already a dollar in there from the initial setting it from 0 to 1. What am I missing? $\endgroup$
    – adaPlease
    Commented Jun 4, 2015 at 18:30
  • $\begingroup$ @adaPlease See the "added" part in the answer. $\endgroup$
    – hengxin
    Commented Jun 5, 2015 at 1:46
  • $\begingroup$ Okay, I still don't get it. In the first version you put first dollar on a one bit to change it to 1, and second to save later so you can reset it to 0 when a higher bit is needed. Now however there is a reset operation - when it comes, every single one bit will have a dollar on it, including the highest order one. Consider 11 with just 3 dollars per increment - you go to 100 and have 1 dollar on highest order and the only 1 from 100 and you set max[A] to 2. Now when reset comes you use up one dollar from this highest order 1, reset max and that's it, you don't need 4th dollar. $\endgroup$
    – adaPlease
    Commented Jun 5, 2015 at 14:07
  • $\begingroup$ @adaPlease well. I think we are following different code for Reset operation. In the web page, it is For i = 0 to max[A] do A[i] = 0. In your example, it seems that you are following For i = 0 to max[A] do if(A[i] != 0) A[i] = 0. Do you? If you prefer to your code, please feel free to add an explanation on this situation at the end of my answer. $\endgroup$
    – hengxin
    Commented Jun 6, 2015 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.