1. 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.

2. 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.

- What is the worst-case running time of increment?

- What is the worst-case complexity for a sequence of k-increment?

- Use the potential method to find a better estimate.

3. 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 dont implement the union-by-size and path compression techniques.

4. Repeat exercise (3) assuming that we now implement both techniques