CS535 Homework 2
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.
2023-09-21