Introduction to Algorithms March 9, 2011Massachusetts Institute of Technology 6.006 Spring 2011Professors Erik Demaine, Piotr Indyk, and Manolis Kellis Quiz 1 SolutionsQuiz 1 SolutionsProblem 1. True or False [21 points] (7 parts)For each of the following questions, circle either T (True) or F (False). Explain your choice.(Your explanation is worth more than your choice of true or false.)(a) T F The height of any binary search tree with n nodes is O(log n).Explain:Solution: False. In the best case, the height of a BST is O(log n) if it is bal-anced. In the worst case, however, it can be Θ(n).(b) T F Inserting into an AVL tree with n nodes requires Θ(log n) rotations.Explain:Solution: False. There were two ways you can show this.1. There are cases where inserting into an AVL tree requires no rotations. Θ(log n)rotations implies Ω(log n) rotations. Since we have insertions that require norotations, this means that inserting into an AVL tree does not require Ω(log n)rotations and thus it does not require Θ(log n) rotations.2. Inserting into an AVL tree may look at O(log n) nodes, but it only needs toperform at most 2 rotations to fix the imbalance. Thus inserting into an AVL treerequires O(1) rotations, which is not Θ(log n).Both of these were acceptable.Common mistakes included thinking that rotations needed to be made for eachnode in an inserted node’s ancestry line and misunderstanding the problem tothink that we were asking for the runtime of insertion and not the number ofrotations required.6.006 Quiz 1 Solutions Name 2(c) T F The depths of any two leaves in a max heap differ by at most 1.Explain:Solution: True. A heap is derived from an array and new levels to a heap areonly added once the leaf level is already full. As a result, a heap’s leaves are onlyfound in the bottom two levels of the heap and thus the maximum differencebetween any two leaves’ depths is 1.A common mistake was pointing out that a heap could be arbitrarily shaped aslong as the heap property (parent greater than its children in the case of a max-heap) was maintained. This heap is not a valid heap, as there would be gaps if wetried to express it in array form, heap operations would no longer have O(log n)running time, and heap sort would fail when using this heap.Another common mistake was simply justifying this statement by saying a heapis balanced. An AVL tree is also balanced, but it does not have the property thatany two leaves have depths that differ by at most 1.(d) T F A tree with n nodes and the property that the heights of the two children of anynode differ by at most 2 has O(log n) height.Explain:Solution: True. Using the same approach as proving AVL trees have O(log n)height, we say that nhis the minimum number of elements in such a tree of heighth.nh≥ 1 + nh−1+ nh−3(1)nh> 2nh−3(2)nh> 2h/3(3)h < 3 lg nh(4)h = O(log n) (5)Grading was fairly tight on this one. Most of the answers that got full credit werethe ones that was able to show the reduction above or something similar. Manyanswers did not have enough justification, though stated true statements (e.g. “ifthe heights of every node’s two children differ by at most some constant c, thetree will have height O(log n)”, true but we’re looking for why exactly). Somegot to the right conclusion with an alternate method but had some logical flaws.A common mistake was providing a counter example where the height was greaterthan log n. This is not a valid counter example since that’s not what O(log n)height means. h = O(log n) is comparing the asymptotic relationship betweenthe height and the number of elements in the tree, it’s not saying h < log n forall n.6.006 Quiz 1 Solutions Name 3(e) T F For any constants x, y > 1, we have nx= O(yn).Explain:Solution: True. Exponential growth always dominates polynomial growth. Toshow more rigorously, we want to show thatnxyn= 0 as n goes to infinity. Forlarge enough n, we have0 <log nn<log yx + 1(x + 1) log n < n log ynx+1< yxnxyn<1nSince1n= 0 as n goes to infinity, this shows thatnxyn= 0 for the same limit andthus nx= O(yn). This proof was not necessary for full credit.(f) T F Let |U| = m2and consider hashing with chaining. For any hash function h :U → {1, 2, . . . , m − 1}, there exists a sequence of m insertions that leads to achain of length m.Explain:Solution: True. Consider any h. By pigeonhole principle, there exists at leastone bucket j ∈ {1, 2, . . . , m − 1} in the hash array such that there is a set Sof m2/(m − 1) > m universe elements iıU such that h(i) = j for all i ∈ S.Inserting all elements in S creates a chain of sufficient length.Most answers were correct. Some incorrect arguments assumed that h is a ran-dom function (using simple uniform hashing assumption) - this assumption can-not be made here because we are dealing with any function h. A few otheranswers suggested using perfect hashing to show the answer is False. This doesnot work: a perfect hash function is constructed for a specific set S, while in thequestion we are given h upfront, and want to construct a “bad” set for it.6.006 Quiz 1 Solutions Name 4(g) T F Five elements can always be sorted with at most seven comparisons in the com-parison model.Explain:Solution: This question turned out to be “unfortunate”. As such, we decidedto award 3 points to any answer.The answer to the question is True - there is a way to sort 5 elements using 7comparison. Unfortunately, the answer is tricky, and no one got it right.The answer is yes but in order to justify this you would need to give an actualalgorithm (or give the decision tree) for sorting any 5 elements in 7 comparisons.Here is very clever way to do this1:Compare A to B and C to D. Without loss of generality (WLOG), supposeA > B and C > D. Compare A to C. WLOG, suppose A > C. Sort E intoA-C-D. This can be done with two comparisons. Sort B into {E, C, D}. Thiscan be done with two comparisons, for a total of seven.On the other hand, there was a great variety of incorrect solutions to this ques-tions. For clarity, we partition them into two categories: incorrect solutions yield-ing a correct answer, and incorrect solutions yielding an incorrect answer.In the first category, the dominant argument was to compare 27= 128 (the maxi-mum number of leaves in a decision tree of height 7) to 5! = 120 (the number ofdifferent orderings of 5 elements), and argue that since 128 > 120 the algorithmmust exist. Unfortunately, this only shows that the
View Full Document
Unlocking...