ICS 261, Fall 2011, Homework 1 Due Wednesday, October 5, 2011. 1. Consider the problem of maintaining a binary counter, with two operations: initialize a new counter to zero, and add one to the value in the counter. Suppose that the actual time to initialize the counter is 1 second, and the actual time to increment the counter is b seconds, where b is the number of bits in the binary value that change in the increment step. (a) Use the potential function Phi = the number of nonzero bits in the counter value, and the potential method of amortized analysis (http://en.wikipedia.org/wiki/Potential_method) to show that the amortized time per operation of this structure is O(1). (b) Suppose we modify our API to include a new operation that decreases the counter value by one. Again, the actual time for this operation is b seconds, where b is the number of bits that change. Explain why there cannot be a constant amortized time bound for this modified structure. 2. Define a factorial tree to be a structure where the nodes at level i (counting the root as level 1) have exactly i children, so that the total number of nodes at level i is i!. Then it can be shown that a complete factorial tree with n nodes (that is, a tree with n nodes in which all but the last level have the same structure as a factorial tree, and in which the nodes in the last level are as far to the left as possible) has height O(log n / log log n). (a) Suppose we use a complete factorial tree to define a priority queue structure, with the same update operations as the binary heap and D-ary heap but using a factorial tree in place of a complete D-ary tree. What would be the time to decrease one of the keys in the priority queue? Use O-notation. (b) For the same factorial heap data structure, what would be the time to delete the minimum key? 3. (a) Describe how to form, for any n, a sequence of Fibonacci heap operations that will lead to a heap structure in which all n nodes form a single path of height n. (b) After the sequence of operations you describe, what will happen to your Fibonacci heap if you perform a single operation that decreases the priority on the node with maximum priority (the one farthest from the root of the path)?