In the example of incrementing a k-bit binary counter taught in class, we showed that the amortized cost of an INCREMENT operation is O(1). We now support one more operation called RESTART, which sets all the bits of the binary counter to 0.

This question will ask you to implement a counter as a bit array so that any sequence of n INCREMENT and RESTART operations takes O(n) time starting from an initially zero counter.

(i) [5 marks] The key strategy of achieving this is to record the position of the most signicant 1 bit in the binary counter and keep it up-to-date when we perform operations. Write down the pseudocode for INCREMENT and RESTART, to show how to maintain such information. Make your solution as ecient as possible. Describe your idea in English in addition to giving pseudocode, but you need not argue about correctness or analyze the running time.

(ii) [5 marks] Now, perform amortized analysis to prove that your solution in (i) guarantees that any sequence of n INCREMENT and RESTART operations takes O(n) time starting from an initially zero counter. Hint: One solution uses the potential method. Under the potential function of this method, some operations may have negative amortized cost. This is however ne. Why? Think about what conclusion can be drawn when an operation has negative amortized cost with respect to a particular potential function that starts out at 0 and always remains nonnegative.