March 12 2008 6 006 Spring 2008 Quiz 1 Introduction to Algorithms Massachusetts Institute of Technology Professors Srini Devadas and Erik Demaine Quiz 1 Do not open this quiz booklet until you are directed to do so Read all the instructions on this 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 120 points This quiz booklet contains 10 pages including this one Two extra sheets of scratch paper are attached Please detach them before turning in your quiz at the end of the exam period 00 This quiz is closed book You may use one 8 21 1100 or A4 crib sheet both sides No calculators or programmable devices are permitted Write your solutions in the space provided If you need more space write on the back of the sheet containing the problem Do not put part of the answer to one problem on the back of the 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 cite known results Do not spend too much time on any one problem Read them all through first and attack them 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 correctness of your answer but also on the clarity with which you express it Be neat Good luck Problem Parts Points Grade Grader 1 1 15 2 1 20 3 2 15 4 2 30 5 1 10 6 1 15 7 2 15 Total 120 Name Circle your recitation time Hueihan Jhuang 10AM 11AM Victor Costan 2PM 3PM 6 006 Quiz 1 Name 2 Problem 1 Asymptotic workout 15 points For each function f n along the left side of the table and for each function g n across the top 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 write only the strongest one The first row is a demo solution for f n n2 g n n2 n1 5 2n f n n lg n n log30 n n3 n n lg n n2 6 006 Quiz 1 Name 3 Problem 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 the asymptotic running time for each of the operations along the top For hashing give the expected running time assuming simple uniform hashing for all other data structures give the worst case running time Give tight asymptotic bounds using notation If we have not discussed how to perform a particular operation on a particular structure answer for the most reasonable implementation you can imagine Operation Insert Extract min Contains Unsorted linked list Sorted linked list Data Structure Min heap Max heap Hashing with chaining and 1 Definitions 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 Minimum 6 006 Quiz 1 Name Problem 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 stores the maximum element Give pseudocode for an efficient algorithm to implement the operation find second maximum A which finds the next to largest key stored in the max 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 Does the following alternate implementation of build max heap work In other words does it 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 4 6 006 Quiz 1 Name 5 Problem 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 merging two sorted lists such as the merging algorithm used in merge sort Then she merges the resulting list of 2n k elements with the third list merges the list of 3n k elements that results with the fourth 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 terms of n and k 6 006 Quiz 1 Name b 20 points Briefly describe an algorithm for merging k sorted lists each of length n k whose worst case running time is O n lg k Briefly justify the running time of your algorithm If you cannot achieve O n lg k do the best you can for partial credit 6 6 006 Quiz 1 Name 7 Problem 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 next page show the resulting tree after rebalancing We also recommend showing intermediate steps for partial credit 60 20 10 75 40 30 70 50 95 90 99 For 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 parent 6 006 Quiz 1 Name 8 60 20 10 75 40 30 70 50 Initial AVL tree 95 90 99 6 006 Quiz 1 Name 9 Problem 6 Honey I shrunk the heap 15 points Suppose we have a heap containing n 2k elements in an array of size n and suppose that we repeatedly extract the minimum element n times never performing insertions To make the heap space efficient we move the heap over to an array of size 2j whenever an extraction decreases the number of elements to 2j for 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 …
View Full Document
Unlocking...