Introduction to Algorithms Massachusetts Institute of Technology Professors Erik Demaine Piotr Indyk and Manolis Kellis March 9 2011 6 006 Spring 2011 Quiz 1 Solutions Quiz 1 Solutions Problem 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 balanced 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 no rotations 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 to perform at most 2 rotations to fix the imbalance Thus inserting into an AVL tree requires O 1 rotations which is not log n Both of these were acceptable Common mistakes included thinking that rotations needed to be made for each node in an inserted node s ancestry line and misunderstanding the problem to think that we were asking for the runtime of insertion and not the number of rotations 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 are only added once the leaf level is already full As a result a heap s leaves are only found in the bottom two levels of the heap and thus the maximum difference between any two leaves depths is 1 A common mistake was pointing out that a heap could be arbitrarily shaped as long as the heap property parent greater than its children in the case of a maxheap was maintained This heap is not a valid heap as there would be gaps if we tried 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 heap is balanced An AVL tree is also balanced but it does not have the property that any 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 any node 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 nh is the minimum number of elements in such a tree of height h nh 1 nh 1 nh 3 nh 2nh 3 1 2 nh 2h 3 h 3 lg nh h O log n 3 4 5 Grading was fairly tight on this one Most of the answers that got full credit were the ones that was able to show the reduction above or something similar Many answers did not have enough justification though stated true statements e g if the heights of every node s two children differ by at most some constant c the tree will have height O log n true but we re looking for why exactly Some got 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 greater than 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 between the height and the number of elements in the tree it s not saying h log n for all n 6 006 Quiz 1 Solutions Name 3 e T F For any constants x y 1 we have nx O y n Explain Solution True Exponential growth always dominates polynomial growth To x show more rigorously we want to show that nyn 0 as n goes to infinity For large enough n we have log n log y 0 n x 1 x 1 log n n log y nx 1 y x nx 1 n y n x Since n1 0 as n goes to infinity this shows that nyn 0 for the same limit and thus nx O y n This proof was not necessary for full credit f T F Let U m2 and consider hashing with chaining For any hash function h U 1 2 m 1 there exists a sequence of m insertions that leads to a chain of length m Explain Solution True Consider any h By pigeonhole principle there exists at least one bucket j 1 2 m 1 in the hash array such that there is a set S of 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 random function using simple uniform hashing assumption this assumption cannot be made here because we are dealing with any function h A few other answers suggested using perfect hashing to show the answer is False This does not work a perfect hash function is constructed for a specific set S while in the question 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 comparison model Explain Solution This question turned out to be unfortunate As such we decided to award 3 points to any answer The answer to the question is True there is a way to sort 5 elements using 7 comparison 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 actual algorithm 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 suppose A B and C D Compare A to C WLOG suppose A C Sort E into A C D This can be done with two comparisons Sort B into E C D This can be done with two comparisons for a total of seven On the other hand there was a great variety of incorrect solutions to this questions For clarity we partition them into two categories incorrect solutions yielding a correct answer and incorrect solutions …
View Full Document
Unlocking...