Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework 2

CS535

Due Date:  September 25th, 2023

CS Department, IIT

1.   (a)  Let B  be the binary representation of the number of elements in a binomial heap.   Consider inserting a node in the heap. Prove that, the number of times two trees in the binomial heap are merged into a bigger tree is equal to the number of bit-flips when B is incremented by 1.

(b)  Consider two binomial heaps H1   and H2 , and let the binary representation of the number of elements in the two heaps, be B1  and B2  respectively.  Prove that while merging H1  and H2 , the number of times two smaller trees are merged into a bigger tree, is equal to the number of carry-overs generated when B1  and B2  are added.

2. In a Fibonacci heap show a sequence of operations that results in a tree with minimum number of nodes.

3. In a Fibonacci heap, suppose a node in a tree is only removed from its parent after loosing k children. Design a potential function and analyze the complexity of the heap for a decrease key operation, an insert operation and a delete operation.

4. In the Fredman-Tarjan algorithm suppose Prof.  G. N. IOUS decides to stop the contraction phases when there are O(V/log V) vertices and then use Prim’s algorithm on the contracted graph.  The claim is that the complexity is improved. Is he correct? Provide the time complexity.

5. In a UNION-FIND data structure with compression, it is conjectured that each node which is part of a FIND will require exactly one unit operation for further FIND’s on that node.  Design a sequence of UNION-FIND operations where this may not be true.