Solutions to homework #4

Sample solutions for hw4

[20.2-7] Incrementing a binary number is essentially the same operation as inserting into a binomial heap. When a binary number is incremented, the possible changes "ripple" to the left until a zero is reached because incrementing a zero does not require a "carry". When an element (binomial tree of order 0) is inserted into a binomial heap which already contains a tree of order 0, the merging of tree pairs occurs until there are no longer two binomial trees of the same order in the heap. Binomial heap Merge is essentially the same operation as addition of two binary numbers. The basic idea is the same as in incrementing a binary number. Since the complexity of Mereg is of the order of the number of bit operations in the corresponding addition, it is O(log n).
[21.2-3] By corollary 20.2 in the Cormen et. al. text, the maximum degree of any node in an n-node binomial tree is lg n. A Fibonacci is lg n. A Fibonacci heap which supports only the mergeable heap operations (Insert, Merge, DeleteMin) is a collection of unordered binomial trees. The largest tree that can exist in such a collection contains n nodes. The largest possible degree is therefore log n.
[21.2-4] Performing consolidation after the insertion and union operations forces all binomial trees in McGee heaps to have different order. This is obviously also the case after DeleteMin. McGee heaps are thus the well known binomial heaps.
[21.2-5] Performing n insertions followed by n DeleteMins effectively sorts the input stream. (One can always argue in terms of inserting into an initially empty PriorityQueue elements of an array and storing them back in the Min order.) Since the comparison based sorting has the lower bound Omega(n log n), not all the 2n operations involved can have constant amortized time complexity.
[21.4-1] Inductively, assume that you have a Fibonacci Heap that has one skewed tree with n-1 nodes and one trivial tree containing one smaller element. By inserting two more elements smaller than any of those present and then deleting the minimum one, consolidation is forced and the two trivial (one node) trees will be linked first, followed by linking the skewed tree to the root of the two node tree. Decreasing key of the small child of the root causes it to be "on its own", beside the skewed tree of n nodes, thus maintaining the invariant "Fibonacci Heap with one skewed tree and one trivial tree". The obvious start is with n=1.
[22.2-2] This procedure links the elements x_{16} through x_1 into a sequential list. Both Find-Set operations return 16.
["A familiar problem on amortized time complexity"] The MaxArr data type is implemented as an array A[1..n] of integers with a pointer Max to the maximum value in A. Each array entry corresponds to the multiplicity of the element equal to its index. For example, A[3] holds the number of 3's in MA.
The worst case time complexity for Initialize is O(n) (unless one knows how to initialize an array in constant time, which requires a slightly more sophisticated data structure), so the amortized time complexity for the operation is O(1), assuming linear total number of MA operations. Increment increases the sum of all elements in MA by one. It "pays" one unit for the cost of incrementing A[1] (counting ones), and one unit for the cost of enlarging the sum of all elements in MA by one (you can think of this sum as the potential function).
DeleteMax operates in linear worst case time (decrementing the entry pointed to by the Max pointer and, if necessary, updating the max pointer). The amortized complexity is constant because the backwards search for the next non-zero entry consumes the extra credits provided by all the Increments creating the deleted entry. Add takes constant time decrementing two entries and incrementing one and possibly updating Max.

Thanks to Adam for providing a draft of this document.