Algorithms Supervision 6

Recommended reading

Chapters 25, 26, 33 of Introduction to Algorithms (3rd edition) by Cormen, Leiserson, Rivest & Stein.

Exercises

1. What are the relative advantages and disadvantages between binary heaps and binomial heaps?
2. Sketch the state of a) a binary min-heap, and b) a binomial min-heap after each of the following operations:
   1. insert(4)
   2. insert(3)
   3. insert(5)
   4. insert(6)
   5. insert(2)
   6. decreaseKey(5,1)
   7. extractMin()
3. 2009 Paper 4 Question 1
4. 2009 Paper 4 Question 2
5. 2003 Paper 5 Question 1, part a) only.
6. The weighted union heuristic reduces the complexity of m disjoint set operations on n elements from O(n²) to O(m + n log(n)).
   1. Without the heuristic, the worst case sequence of operations consists of alternating calls to add_singleton and merge. What is the complexity of this sequence when the weighted union optimisation is used?
   2. Describe properties of a sequence of operations which achieves the new worst case complexity, and give an example sequence.
7. 2004 Paper 6 Question 1 (part c is no longer on the course, but have a go at it if you can)