Problem
I. Suppose we perform a sequence of operations on a queue data structure. After every n operations we make a copy of the entire queue for debugging purposes. Show that the cost of n operations (including the copy) is O(n) using the accounting method.
II. Suppose we have implemented a k-bit counter with a k-element binary array. The counter is initially 0. The only available operation is increment(A) which adds 1 to the current number.
i. What is the worst-case running time of increment?
ii. What is the worst-case complexity for a sequence of k-increment?
iii. Use the potential method to find a better estimate.
III. Suppose we have 20 singleton sets, numbered 0 through 19, and we call the operation union(find(i),fin(i+5)), for i = 0,1,2,.....,14. Draw a picture of the tree-based representation of the sets that result, assuming we don't implement the union-by-size and path compression techniques.
IV. Repeat exercise (III) assuming that we now implement both techniques