May 21 2009 6 006 Spring 2009 Final Exam Introduction to Algorithms Massachusetts Institute of Technology Professors Sivan Toledo and Alan Edelman Final Exam 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 180 minutes to earn 200 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 12 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 three 8 21 1100 or A4 crib sheets 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 Grade Grader Problem Parts Points Grade 1 8 24 5 1 24 2 4 32 6 1 24 3 3 24 7 1 24 4 3 24 8 1 24 Total Name 200 Grader 6 006 Final Exam Name 2 Problem 1 True or False 24 points 8 parts For each of the following questions circle either T True or F False Explain your choice No credit if no explanation given a T F There exists an algorithm to build a binary search tree from an unsorted list in O n time Explain b T F There exists an algorithm to build a binary heap from an unsorted list in O n time Explain c T F To solve the SSSP problem for a graph with no negative weight edges it is necessary that some edge be relaxed at least twice Explain d T F On a connected directed graph with only positive edge weights Bellman Ford runs asymptotically as fast as Dijkstra Explain 6 006 Final Exam Name e T F A Givens rotation requires O 1 time Explain f T F In the worst case merge sort runs in O n2 time Explain g T F There exists a stable implementation of merge sort Explain h T F An AVL tree T contains n integers all distinct For a given integer k there exists a lg n algorithm to find the element x in T such that k x is minimized Explain 3 6 006 Final Exam Name Problem 2 Short Answer 32 points 4 parts a The eccentricity u of a vertex u in a connected undirected unweighted graph G is the maximum distance from u to any other vertex in the graph That is if u v is the shortest path from u to v then u maxv V u v Give an efficient algorithm to find the eccentricity of a given vertex s Analyze its running time b What is the asymptotic cost of solving a linear system of equations with n 1 equations of the form ai i xi ai i 1 xi 1 bi i 1 n 1 and one equation of the form an 1 x1 an 2 x2 an n xn bn none of the a s in this equation are zero The a s and b s are given numbers and the x s are unknowns Assume that we use Givens rotations to reduce the coefficient matrix to a triangular form Justify your answer 4 6 006 Final Exam Name c Suppose a hash function h maps arbitrary keys to values between 0 and m 1 inclusive We hash n keys k1 k2 kn If h ki h kj we say that ki and kj collide Assuming simple uniform hashing how should we choose m in terms of n such that the expected number of collisions is O 1 Justify your answer d Suppose you have a directed acyclic graph with n vertices and O n edges all having nonnegative weights Propose an efficient method of finding the shortest path to each vertex from a single source and give its running time in terms of n 5 6 006 Final Exam Name 6 Problem 3 Judge Jill 24 points 3 parts Judge Jill has created a web site that allows people to file complaints about one another Each complaint contains exactly two names that of the person who filed it and that of the person he she is complaining about Jill had hoped to resolve each complaint personally but the site has received so many complaints that she has realized she wants an automated approach She decides to try to label each person as either good or evil She only needs the labeling to be consistent not necessarily correct A labeling is consistent if every complaint labels one person as good and the other person as evil and no person gets labeled both as good and evil in different complaints a 8 points Propose a way to model the consistent labeling problem as a graph problem 6 006 Final Exam Name b 10 points Propose an efficient algorithm to consistently label all the names as good or evil or to decide that no such classification exists Use the graph model you proposed in the previous part of the problem Analyze the running time of the algorithm c 6 points Later Judge Jill wants to be more thorough She will interview some people to figure out who is good and who is evil She can always determine whether a person is good or evil by interviewing him or her Assuming that one person in every complaint is good and the other is evil what is the minimum number of people she needs to interview to correctly classify all the people named in the complaints 7 6 006 Final Exam Name 8 Problem 4 Bitdiddle Bins 24 points 3 parts Ben Bitdiddle has devised a new data structure called a Bitdiddle Bin Much like an array or a set you can I NSERT values into it and you can L OOKUP values to see if they are contained in the structure He ll figure out D ELETE later A Bitdiddle Bin is implemented as a pair of lists arrays designated the neat list and the messy list with these properties The neat list is always in sorted order The messy list may or may not be sorted The messy list has a size of at most n where n is the total number of values in the entire Bitdiddle Bin The L OOKUP algorithm for a Bitdiddle Bin is as follows 1 Use binary search to look for the value in the neat list 2 If it …
View Full Document
Unlocking...