Introduction to Algorithms March 12, 2008Massachusetts Institute of Technology 6.006 Spring 2008Professors Srini Devadas and Erik Demaine Quiz 1Quiz 1• Do not open this quiz booklet until you are directed to do so. Read all the instructions onthis page.• When the quiz begins, write your name on every page of this quiz booklet.• This quiz contains 7 problems, some with multiple parts. You have 120 minutes to earn 120points.• This quiz booklet contains 10 pages, including this one. Two extra sheets of scratch paperare attached. Please detach them before turning in your quiz at the end of the exam period.• This quiz is closed book. You may use one 81200× 1100or A4 crib sheet (both sides). Nocalculators or programmable devices are permitted.• Write your solutions in the space provided. If you need more space, write on the back of thesheet containing the problem. Do not put part of the answer to one problem on the back ofthe sheet for another problem, since the pages may be separated for grading.• Do not waste time and paper rederiving facts that we have studied. It is sufficient to citeknown results.• Do not spend too much time on any one problem. Read them all through first, and attackthem in the order that allows you to make the most progress.• Show your work, as partial credit will be given. You will be graded not only on the correct-ness of your answer, but also on the clarity with which you express it. Be neat.• Good luck!Problem Parts Points Grade Grader1 1 152 1 203 2 154 2 305 1 106 1 157 2 15Total 120Name:Circle your recitation time:Hueihan Jhuang: (10AM) (11AM) Victor Costan (2PM) (3PM)6.006 Quiz 1 Name 2Problem 1. Asymptotic workout [15 points]For each function f (n) along the left side of the table, and for each function g(n) across thetop, write O, Ω, or Θ in the appropriate space, depending on whether f(n) = O(g(n)), f (n) =Ω(g(n)), or f(n) = Θ(g(n)). If more than one such relation holds between f (n) and g(n), writeonly the strongest one. The first row is a demo solution for f (n) = n2.g(n)n n lg n n2n2Ω Ω Θn1.5√2nf(n)n√lg nn log30nn36.006 Quiz 1 Name 3Problem 2. Table of Speed [20 points]For each of the representations of a set of elements along the left side of the table, write down theasymptotic running time for each of the operations along the top. For hashing, give the expectedrunning time assuming simple uniform hashing; for all other data structures, give the worst-caserunning time. Give tight asymptotic bounds using Θ notation. If we have not discussed how toperform a particular operation on a particular structure, answer for the most reasonable implemen-tation you can imagine.OperationInsert Extract-min Contains MinimumUnsortedlinked listSortedlinked listDataStructure Min heapMax heapHashing withchaining andα = 1Definitions of operations:• Insert(S, x): add element x to the set S.• Extract-min(S): remove the minimum element from the set S and return it.• Contains(S, x): return whether element x is in the set S.• Minimum(S): return the minimum element in set S (without extraction).6.006 Quiz 1 Name 4Problem 3. Indie heap operations [15 points] (2 parts)(a) [10 points] Suppose you have a max-heap stored in an array A[1..n], where A[1] storesthe maximum element. Give pseudocode for an efficient algorithm to implement theoperation find-second-maximum(A), which finds the next-to-largest key stored in themax-heap A. Your algorithm should not modify the heap.(b) [5 points] Suppose you have an array A[1..n] of n elements in arbitrary order. Doesthe following alternate implementation of build-max-heap work? In other words, doesit correctly build a max heap from the given elements A[1..n]? Why or why not?build-max-heap(A):for i from 1 to n/2:max-heapify(A, i)This algorithm calls heapify starting at the root and working its way down the tree,instead of the other way around.6.006 Quiz 1 Name 5Problem 4. Madly merging many menus [30 points] (2 parts)Professor Sortun uses the following algorithm for merging k sorted lists, each having n/k elements.She takes the first list and merges it with the second list using a linear-time algorithm for mergingtwo sorted lists, such as the merging algorithm used in merge sort. Then, she merges the resultinglist of 2n/k elements with the third list, merges the list of 3n/k elements that results with thefourth list, and so forth, until she ends up with a single sorted list of all n elements.(a) [10 points] Analyze the worst-case running time of the professor’s algorithm in termsof n and k.6.006 Quiz 1 Name 6(b) [20 points] Briefly describe an algorithm for merging k sorted lists, each of lengthn/k, whose worst-case running time is O(n lg k). Briefly justify the running timeof your algorithm. (If you cannot achieve O(n lg k), do the best you can for partialcredit.)6.006 Quiz 1 Name 7Problem 5. Being Adel’son-Vel’ski˘ı & Landis [10 points]Suppose that we insert 42 into the AVL tree below using the AVL insertion algorithm. On the nextpage, show the resulting tree after rebalancing. We also recommend showing intermediate stepsfor partial credit.603070 95102050 90409975For reference, we include the Python code for AVL insertion, written in terms of rotations:def insert(self, t):node = bst.BST.insert(self, t)while node is not None:if height(node.left) >= 2 + height(node.right):if height(node.left.left) >= height(node.left.right):self.right_rotate(node)else:self.left_rotate(node.left)self.right_rotate(node)elif height(node.right) >= 2 + height(node.left):if height(node.right.right) >= height(node.right.left):self.left_rotate(node)else:self.right_rotate(node.right)self.left_rotate(node)node = node.parent6.006 Quiz 1 Name 8603070 95102050 90409975Initial AVL tree6.006 Quiz 1 Name 9Problem 6. Honey, I shrunk the heap [15 points]Suppose we have a heap containing n = 2kelements in an array of size n, and suppose that werepeatedly extract the minimum element, n times, never performing insertions. To make the heapspace efficient, we move the heap over to an array of size 2jwhenever an extraction decreases thenumber of elements to 2jfor any integer j. Suppose that the cost of each such move is Θ(2j).What is the total movement cost caused by n extract-mins starting from the heap of n elements?(Ignore the Θ(n lg n) cost from the heapify operations themselves.)6.006 Quiz 1 Name 10Problem 7. Trash hees [15 points] (2 parts)Suppose we store n elements in an m-slot hash table using chaining, but we
View Full Document
Unlocking...