1. In Fibonacci heaps, there is a suggestion that we be allowed to delete 2-child nodes at a node before requiring that a CASCADING-CUT occurs. What is the complexity of insertion/deletion

2. Union-Find: Suppose all UNION operations are done before the FIND operations. Show that m FIND operations require O(m) operations. You should use a potential functions argument

3. Given a machine with time span T and a set of jobs each having a profit pi and required time ti, the goal is to maximize the summed profit of jobs scheduled on the machine. Consider the following algorithm for job scheduling: Sort the jobs in decreasing order by pi/ti and schedule them until you cannot fit more. Prove or disprove the correctness of this greedy algorithm

4 Show that the matric subset problem is a matroid.

5. Give an efficient implementation of Huffman encoding and analyze its time complexity

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