COMPUTER SCIENCE TRIPOS Part IA – 2016 – Paper 1
Algorithms (TMS)
(a) State whether each of the following six forests can be generated from an empty
Fibonacci Heap using the standard operations. If it cannot be generated, clearly
state the condition or property of Fibonacci Heaps that is violated.
Note: Marked nodes are in boldface. [9 marks]
58 30 10
43 41 33 70 32
54 38 82 51
min
(i)
22 14 65
70
18
25 27
33
min
(ii)
23
27 45
35
38 39
20
min
(iii)
30 35
43 36 33 40
35 55 81
min
(iv)
23
27 45
35
38 39
min
(v)
23
27 26 39
35 41 45
50
min
(vi)
(b) Consider the operations Insert, Extract-Min, and Decrease-Key in a
Fibonacci Heap. Answer the following for each of the three operations.
(i) What are the worst-case actual costs? [3 marks]
(ii) What are the worst-case amortized costs? [3 marks]
(c) Consider the following modification to Fibonacci Heaps. Instead of marking a
node once it has lost its first child, we mark a node once it has lost two of its
children. How would you adjust the analysis of the maximum degree d(n)?
[5 marks]