Carnegie Mellon University, Computer Science Department Graduate Algorithms 15-750, Spring 2004, Instructor: Manuel Blum TA: Doru Balcan Homework Assignment #3 --- SOLUTIONS 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"?) Solution: There is no contradiction in saying that the O(m + n*log(n)) time bound for Dijkstra's algorithm is both a worst-case AND an amortized upper bound. The amortization refers to the "distribution" of the computational cost accross the set of Fibonacci Heap operations. So, when we say that Dijkstra algorithm's running time is "amortized O(m+n*log(n))", we refer to this sequence of operations. On the other hand, this upper bound is in itself a worst-case upper bound. More precisely, if we don't see the algorithm as consisting of a series of operations, but as a "single step" (sort of...), the worst-case cost of this "step" is O(m+n*log(n)). 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.) Solution: The "m" term is necessary, since we can't afford not to look at every edge. It is easy to imagine situations, in which renouncing to look at an edge generates the algorithm produce a wrong answer. 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) Solution: ____________________________________________________________________ Operation | Running time | name | Trivial Heaps | Fibonacci Heaps | ____________________________|_________________|___________________| - makeheap(i) | O(1) | O(1) | -----------------------------------------------|-------------------| - findmin(h) | O(1) | O(1) | -----------------------------------------------|-------------------| - insert(h,i) | O(1) | O(1) | -----------------------------------------------|-------------------| - meld(h,h') | O(1) | O(1) | -----------------------------------------------|-------------------| - deletemin(h) | O(n) | O(log n) | -----------------------------------------------|-------------------| - decrement(h,i,D) | O(1) | O(1) | -----------------------------------------------|-------------------| - delete(h,i) | O(n) | O(log n) | -----------------------------------------------|-------------------| - heapify(a_1, ..., a_n) | O(n) | O(n) | -------------------------------------------------------------------| It's pretty strightforward to see that considering amortized running time for the operation on Trivial Heaps is equivalent to worst-case running time (that will become obvious when we explain how we can achieve these time bounds). We won't explain why these (amortized) running time bounds are obtained for Fibonacci Heaps. Here's how we get the running time for the operations on Trivial Heaps. - makeheap(i) - we just make a list with an element; it will be the minimum element - O(1) - findmin(h) - we obtain the minimum element in oone step, since we know (by TH definition) we have a pointer to it - O(1) - insert(h,i) - we add the new element to the heap, and the only thing we need to check is whether it is smaller than the minimum element so far; if so, make the min-pointer point to it O(1) - meld(h,h') - we need just to compare the min-elements in heaps h and h'; the min-pointer of the new heap shall point to whichever of these two elements is smaller - deletemin(h) - O(n), since after deletion we need to find the new smallest element - decrement(h,i,D) - after decrementing, we need to verify if the new element i is now the smallest; if so, min-pointer shall point to it; thus, we need O(1) for this operation - delete(h,i) - if i is the minimum element, it takes O(n) (just as for deletemin). Here is the trickiest case for worst-case/amortized equivalence: in the worst possible sequence of deletions, we may need n+(n-1)+...+1 time steps, and so O(n) on average. (Remember that amortized cost is the worst average cost over all possible sequences of operations.) - heapify(a_1, ..., a_n) - clearly O(n); we need to create the heap and find the minimum (in the process). 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? Solution: a. As discussed in class, a Binomial Heap with n elements is made of trees B_i_1, B_i_2, ..., B_i_k iff the where i_j (1<=j<=k) are the positions containing 1's in the binary representation of n. (We are obviously discussing the case of eager melding here.) As a result of this observation, the structure of the Binomial Heap with 53 elements is: B_0 B_1 B_2 B_3 B_4 B_5 o nil o nil o_______ o__ |\ |\ \ \_ / \ \__ o o o o o o__ / \ \__ | | |\ |\ \ / B_4 \ o o o o o o o o --------- / \ | |\ / \ o o o / B_4 \ | --------- o (This happens because 53_10 = 110101_2) b. We can prove by induction that the number of items at level k of the binomial tree B_i, is "i choose k" (the corresponding "binomial coefficient"). The base case is trivial. Assume the property holds for i-1, and we want to prove it for i. By definition, binomial tree B_i is made of two binomial trees of the form B_{i-1}, linked such that one of them is a subtree of the other (we can say that tree B''_{i-1} is linked to tree B'_{i-1}). Then, the number of elements on level k in B_i, is equal to the sum of the number of elements on level k in B'_{i-1} and the number of elements on level k-1 in B''_{i-1}. But from the induction hypothesis, we get the desired result, since the binomial coefficients satisfy the equation / i \ /i-1\ /i-1\ | | = | | + | | \ k / \ k / \k-1/ 5. a. Can a Fibonacci Heap contain a tree 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.) Solution: a. No. It would violate the condition that the i-th child of the root have rank at least i-2. Of course, the fourth child of the root should have rank >= 2, which is clearly not the case. b. Yes! As a proof, we'll give an actual construction of the Fibonacci heap, consisting of only this tree. min min min min / / / / V V (mark node) V V o o o o o o* o o* | |\ delete(1) | | delete min |\ delete(2) | o o o -------> o o ---------> o o -------> o 1 | | 2 | (unmark) | o o o ( node ) o | | o o NOTE: A common mistake would be to say that, "since the smallest tree of height 3 is F_5, the 4-node chain tree can't belong to a Fibonacci Heap". Well, here is obviously a confusion: F_5 is the smallest tree of RANK 5, not of HEIGHT 3! The 4-node chain is a tree of rank 1, which obviously doesn't contradict the condition mentioned in Theorem 9.1 (the rank of the i-th child is at least i-2).