CompSci 261, Spring 2017, Homework 5

1. Suppose that you create a new Fibonacci heap, insert 65 elements into it, and then perform a single remove-min operation. How many trees will the resulting Fibonacci heap have, and how many nodes will be in each tree?

   (Hint: if you perform a remove-min of a Fibonacci heap in which all trees have a single elements, what are the possible sizes of the resulting trees?)

   Solution: After a remove-min, from a heap of single-element trees, the trees will become merged in pairs so that they have distinct power-of-two sizes. Therefore, there will only be one 64-node tree.

2. Suppose that you have an implementation of a priority queue in which only three operations are allowed: create an empty heap, add an element, and remove-min. Your implementation takes actual time $O(1)$ to create an empty heap, and actual time $O(\log n)$ for the other two operations, where $n$ is the number of elements currently in the heap. Find a potential function $\Phi$ such that, with this potential function, the amortized time of an add-element operation is still $O(\log n)$ but the amortized time of a remove-min becomes $O(1)$.

   Solution: $\Phi=n\log n$. Adding an element increases $\Phi$ by $\log n + O(1)$, so the amortized time stays $O(\log n)$. Removing an element decreases $\Phi$ by $\log n - O(1)$, cancelling most of the actual time for that operation and leaving amortized time $O(1)$.

3. For which values of $n$ does an $n$-element binary heap have an element with exactly one child, and where in the heap is that element and its child?

   Solution: The only elements that could be its parent's only child is at position $n-1$, and it is the only child if and only if $n$ is nonzero and even. Its parent is at position $n/2-1$.

4. A hypercube graph of dimension $d$ has $2^d$ vertices and $d2^{d-1}$ edges. (For instance, the three-dimensional cube has 8 vertices and 12 edges.) Suppose that we are going to run Dijkstra's algorithm on this graph, using a $k$-ary heap for the priority queue. What would be the best choice of $k$ to use (the one that causes the algorithm to run as quickly as possible), and what would be the running time of the algorithm with this choice?

   Both of your answers should be expressed as formulas involving $d$. The running time should use $O$-notation. The choice for $k$ should just be a formula, without $O$-notation, but you can simplify your answer to this part by omitting any constant factors from this formula, as they will not affect the $O$-notation for the running time.

   Solution: For a graph with $n$ vertices and $m$ edges, a good choice is $k=m/n$, giving time $O(m\log_{m/n}n)$. Here, $n=2^d$ and $m=d2^{d-1}$, so (ignoring the extra factor of two, which doesn't change the $O$-notation) we can take $k=d$ and get time $$O\left(\frac{d^2 2^d}{\log d}\right),$$ faster by a $\log d$ factor than the binary heap.