1. (a) What is the smallest possible number of nodes that could be formed in one of the trees of a Fibonacci heap, if the root node of the tree has five children?
(b) Draw a tree that realizes this minimum number of nodes and could be formed as part of a Fibonacci heap.
(c) In your tree, which nodes must necessarily have their flag set to True?


2. (a) In a Fibonacci heap with 100 items in it, what is the maximum number of trees possible?
(b) In a Fibonacci heap with 100 items in it, what is the maximum number of children that any node might possibly have?

3. Suppose that we are attempting to analyze Fibonacci heaps using a potential function Phi=t+f where t is the number of trees in the heap and f is the number of flagged nodes (without the factor of 2 used in the correct potential function).
(a) With this potential function, would the amortized time for a delete-min operation still be O(log n)? Why or why not?
(b) With this potential function, would the amortized time for a decrease-key operation still be O(1)? Why or why not?

4. Suppose that we are using Dijkstra's algorithm on a graph with n vertices and at most three outgoing edges per vertex. Suppose also that each edge weight is a positive integer and is at most n.
(a) What would be the running time for this algorithm, using O-notation as a function of n, if we used binary heaps as the priority queue structure?
(b) What would be the running time for this algorithm if we used Fibonacci heaps as the priority queue structure?
(c) What is the largest number that might occur as a priority during the course of the algorithm?
(d) What would be the running time for this algorithm if we used van
emde Boas trees as the priority queue structure? You should only analyze
the time for the updates to the structure; do not include the time to
initialize it.