Introduction to Algorithms Massachusetts Institute of Technology Professors Srini Devadas and Constantinos Costis Daskalakis March 11 2009 6 006 Spring 2009 Quiz 1 Quiz 1 Do not open this quiz booklet until 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 You have 120 minutes to earn 100 points 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 This quiz booklet contains 7 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 12 1100 or A4 crib sheet both sides No calculators or programmable devices are permitted No cell phones or other communications 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 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 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 1 3 10 2 2 20 3 1 15 4 1 15 5 1 20 6 2 20 Total Grade Grader 100 Name Friday Recitation 1 point Krzysztof 11 AM Alex 12 PM Zoran 3 PM Rishabh 4 PM 6 006 Quiz 1 Name 2 Problem 1 Asymptotic orders of growth 9 points 3 parts For each of the three pairs of functions given below rank the functions by increasing order of growth that is find any arrangement g1 g2 g3 of the functions satisfying g1 O g2 g2 O g3 lg n represents logarithm of n to the base 2 a f1 n 8 n f2 n 251000 f3 n 3 lg n b f1 n 1 100 f2 n n1 f3 n lg n n c 3 f1 n 2lg n f2 n nlg n f3 n lg n 6 006 Quiz 1 Name 3 Problem 2 Balanced Augmented BST 20 points 2 parts In this question we use balanced binary search trees for keeping a directory of MIT students We assume that the names of students have bounded constant length so that we can compare two different names in O 1 time Let n denotes the number of students a Say we have a binary search tree with students last names as the keys with lexicographic dictionary ordering Let k be the number of students whose last name starts with a given prefix x For example if the tree contains 5 names ABC ABD ADA ADB ADC there are k 2 names ABC and ABD respectively starting with the prefix x AB How can we output a list of all those students in O k log n time b Give an algorithm to return the number of nodes k with names starting with a given prefix x in O log n time You are allowed to augment the binary search tree nodes 6 006 Quiz 1 Name 4 Problem 3 Employee Dictionary 15 points 1 part We are interested in building a phonebook for the employees of a small company of size 64 using a dictionary Our hash table will have size m 64 and the employees last names will be used as keys The longest employee name is 15 characters long so to simplify our task we convert every last name into a 15 character string by introducing space characters in front of the first character For instance the last name Devadas will be padded with 8 space characters preceding the leading D Now we encode every letter of the English alphabet together with the space character into a unique 6 bit binary number so that every last name can be represented uniquely by a 90 bit binary number Consider the following hash functions for our dictionary Which of them is likely to perform the best Justify your choice For the hash functions you rejected describe a collection of last names for which the hash function performs poorly and explain why For the hash function of your choice explain why it is better than the other hash functions The input k to the following functions is the 90 bit binary number corresponding to a last name 1 h k k mod 64 2 h k a k mod 218 12 for a 4097 3 h k a k mod 290 84 for a 1 26 54605 Note Observe that 4097 1 212 and 54605 11010101010011012 The operator is the right shift operator 6 006 Quiz 1 Name 5 Problem 4 Asymptotic Runtime Analysis 15 points 1 part Professor Devadas has an idea to assign students to recitations based on their Quiz 1 grades He wants to split all N students into 4 recitations such that the maximum difference between the Quiz 1 grades of any two students in the same recitation is as small as possible To figure out if this idea is reasonable he wants to know how small the staff can make this maximum difference Let the number of students be N and suppose that Quiz 1 scores are all integers in the range 1 M Professor Daskalakis suggests the following Python code which takes the value of M and a pre sorted list of quiz scores def assign recitations M scores N len scores a 1 b M while a b c a b 2 groups 1 group low scores 0 for i in range N if scores i group low c groups groups 1 group low scores i if groups 4 b c else a c 1 return a What is the asymptotic running time of this algorithm Express your answer as a function of N and or M using notation 6 006 Quiz 1 Name 6 Problem 5 Airplane Scheduling 20 points 1 part Logan airport management asks you to compute the airport load during one day which is the maximum number of planes that are on the ground at the same time You are provided the data for n airplanes arrival and departure times To simplify computation the day is divided into m time segments and only these segments are recorded For the plane i start i denotes the time segment of arrival and end i denotes the time segment of departure 1 start i end i m A plane is considered to be on the ground during arrival and departure time segments as well as all segments in between For example if n 5 m 10 and planes arrival departure pairs are 5 7 1 3 8 10 2 5 4 9 then the airport load is 3 during time segment 5 planes 1 4 and 5 are on the ground Give an O m n time algorithm to find the airport load …
View Full Document
Unlocking...