CS 261, Spring 2013, Homework 4 Due Thursday, May 9


1. Suppose that a binary heap contains the four values 1, 2, 3, and 4
(with smaller numbers meaning higher priority). List all of the
permutations of these values that represent valid configurations of the
heap.

    1234, 1243, and 1324


2. Suppose that we have a binary heap with n numbers in it, again with
smaller numbers meaning higher priority. We know that the minimum of the
numbers is in position 0 of the heap. How many different positions could
possibly hold the maximum of the numbers? (You should assume that all
the numbers are different from each other.)

    ceiling(n/2). Using the formulas left child = 2x+1, right child =
    2x+2, it is easy to see that the final ceiling(n/2) cells of a
    binary heap are the cells that don't have any children, and the
    maximum could be in any one of those cells.


3. Consider the following naive representation of a priority queue: we
represent the queue as a dynamic array of the data values, with no
constraints on how they are ordered. To find the minimum value, we
search through the whole array.

(a) What are the amortized time bounds for the add, decrease priority,
and delete min operations in this structure? Give your answers in
O-notation as a function of n, the number of values in the priority
queue.

    add: O(1) (just add it to the end)
    decrease priority: O(1) (assuming you have some way of going
        from the item whose priority you want decreased to its
        position, e.g. using a separate hash table).
    delete min: O(n) (because you have to find the minimum first)

(b) If we are using a priority queue to implement Dijkstra's shortest
path algorithms, are there graphs for which this naive method would lead
to a total time bound that is the same as or better than the bound given
by using Fibonacci heaps? If yes, describe these graphs. If no, explain
why not.

    Yes: the graphs with Omega(n^2) edges. In these graphs,
    Dijkstra's algorithm takes Theta(n^2) time with either data structure.
    But (if the priority queue is initialized to contain all vertices)
    then these are the only graphs for which the naive method is good,
    because it always takes Theta(n^2) time even for sparser graphs.

    In office hours, one student pointed out a different answer: if the
    priority queue contains only the vertices on the current frontier
    (rather than all vertices, as the version of Dijkstra that I
    described it in class uses) then the path graphs also take O(n) time
    either way, because there are only O(1) vertices in the priority
    queue at any time. More generally, the same idea would work whenever
    the graph has the property that the average frontier size is O(m/n).
    However, I don't know of a good description of the graphs for which
    this is always true.


4. Suppose that we perform the following two operations on a Fibonacci
heap: first, create a new heap from a given set of n values, and second,
perform a single delete-min operation. How many trees will there be in
the structure that we finish with, as a function of n?  (Hint: consider
the binary representation of n.)

    There was a typo in the question: the last n should be n-1.
    The answer is: the same as the number of nonzero bits in the
    binary representation of n-1, because all of the trees have
    sizes that are distinct powers of two.