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

SOLUTION: When the counter is incremented, the effect is to change bits from 1 to 0, from the least significant bit upward, until reaching a bit that is already 0 and turning it into a 1, at which point the process stops. So, if b bits are changed, the potential function changes by (b-1)*-1 + 1*+1 = 2 - b.
The total amortized time is O(b) + c(2-b), and if c is chosen to be at least as large as the constant in the O notation then this will cancel leaving O(1) amortized time for the operation.


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

SOLUTION: Consider a sequence of operations that counts up to 2^i, then repeatedly decrements and then increments the number, switching it between 2^i and 2^i-1. The two numbers 2^i and 2^i-1 differ in i+1 positions, so the average time per operation (if we repeat long enough) will be proportional to i. Since i can be chosen arbitrarily, larger than any fixed constant, the average time per operation in this data structure cannot be O(1). And since the total amortized time of a sequence of operations always equals or exceeds the total actual time of the same sequence, the amortized time also cannot be O(1).


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.

SOLUTION: Decreasing a key takes time proportional to the height of the tree, O(log n / log log n).


(b) For the same factorial heap data structure, what would be the time to delete the minimum key?

SOLUTION: Deleting the minimum involves following a path down the tree, comparing the children of each node to determine the smallest child and then comparing the value at the node itself with the value of the smallest child. The time for this is proportional to the total number of children along the path, which is O(1 + 2 + 3 + 4 + ...) = O(log n / log log n)^2.

Incidentally, there was an off-by-one error in the statement of the problem: it should be changed either to say that the nodes at level i have i+1 children, or that the number of nodes at level i is (i-1)!. Fortunately either change has no significant effect on the solution.


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.

SOLUTION: Start by inserting two elements. At this point, you have a single path of height 1 (one of the elements), together with an extra node that is not on this path. Then, as long as you have a path of height i and an extra node, and i is less than n, perform the following sequence of steps:
- Insert another two elements, so you have a path of height i and three extra nodes.
- Delete the extra node that you already had prior to these two insertions. This causes the two new extra nodes to become linked into a two-node tree (a path of height 2), and then it causes the path of height i and the path of height 2 to become linked. If the priorities of the new nodes are chosen carefully, this can be done in such a way that one of the new nodes is the root of the linked tree.
- Decrease the priority of the other new node (the one that is not the root), causing it to become a root of a separate tree. Now you have a path of height i+1 and an extra node again.


(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)?

SOLUTION: Whenever this sequence removes the child from a node x, it happens while x is a root of a tree, so x remains unmarked. Therefore, the decrease-priority operation would only cause the changed node to become a new root, and mark its parent, while not making any other changes to the structure.

It would be possible to give a different answer to (a) that leaves marked nodes within the path. In that case, the answer to (b) would also be different.