Carnegie Mellon University, Computer Science Department
Graduate Algorithms 15-750, Spring 2004,  
Instructor: Manuel Blum
TA: Doru Balcan

  
Homework Assignment #3

Important Note: Each problem is worth 10 points. The solutions are 
expected by Friday, Feb 6, at the beginning of the class 
(IN CLASS). Any hand-ins after this deadline shall not be taken 
into consideration.





1. What kind of upper bound is the O(m + n*log(n)) for Dijkstra's 
algorithm: worst-case, amortized, none or both? Please give details,
explaining your answer. (This upper bound appears in Lecture 9, Kozen).
   (Hint: How come you can say that this bound is "worst-case", when 
it's "amortized"? Wasn't the very purpose of amortized analysis to 
distinguish between these two totally different ways of "counting 
steps"?)






2. In the expression of the running time of Dijkstra's algorithm, 
("O(m + n*log(n))") is term "m" really necessary?
   Extra Credit: Is term "n*log(n)" really necessary? (Suggestion: 
You may try to show that if you could do all the corresponding 
operations faster, then you could also sort faster.)





3. Let's consider a trivially simple data structure, called "Trivial 
Heap". To describe it, let's just say that it is a collection of 
elements, with a pointer to the smallest one. Compare Trivial Heaps 
to Fibonacci Heaps, with respect to running times (for the operations 
Fib. Heaps support). You may compare using either W.C. or amortized.
  For clarification, the operations you're asked to analyze, are:

- makeheap(i)
- findmin(h)
- insert(h,i)
- meld(h,h')
- deletemin(h)
- decrement(h,i,D)
- delete(h,i)
- heapify(a_1, ..., a_n)






4. Binomial Heaps have a rigid structure. For example, a Binomial Heap
on 13 elements has one B_0, no B_1, one B_2, and one B_3.
  a. What is the structure of a Binomial Heap on 53 elements? That is,
what type of Binomial Trees does it contain?
  b. Binomial trees also have a rigid structure. Binomial tree B_i 
has 1 element on depth level 0, i elements on level 1, etc. How many 
elements does it have on level k, where k<=i?






5. a. Can a Fibonacci Heap contain that looks like this?

             o__ 
            /|\ \ 
           / | \  \ 
          /  |  \   \
         /   |   \    \
        o    o    o    o

(The tree has just five nodes: one root, with 4 children.)
 
   b. How about a tree that looks like this?

        o
        |
        |
        o
        |
        |
        o
        |
        |
        o

(The tree is a chain with 4 nodes.)