Introduction to Algorithms May 21, 2009Massachusetts Institute of Technology 6.006 Spring 2009Professors Sivan Toledo and Alan Edelman Final ExamFinal 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 mostprogress.• This quiz booklet contains 12 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 three 81200× 1100or A4 crib sheets (both sides). Nocalculators or programmable devices are permitted. No cell phones or other communicationsdevices are permitted.• Write your solutions in the space provided. If you need more space, write on the back of thesheet 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 citeknown results.• 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 Grader Problem Parts Points Grade Grader1 8 24 5 1 242 4 32 6 1 243 3 24 7 1 244 3 24 8 1 24Total 200Name:6.006 Final Exam Name 2Problem 1. True or False [24 points] (8 parts)For each of the following questions, circle either T (True) or F (False). Explain your choice. (Nocredit if no explanation given.)(a) T F There exists an algorithm to build a binary search tree from an unsorted list inO(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 nec-essary that some edge be relaxed at least twice.Explain:(d) T F On a connected, directed graph with only positive edge weights, Bellman-Fordruns asymptotically as fast as Dijkstra.Explain:6.006 Final Exam Name 3(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 existsa Θ(lg n) algorithm to find the element x in T such that |k − x| is minimized.Explain:6.006 Final Exam Name 4Problem 2. Short Answer [32 points] (4 parts)(a) The eccentricity (u) of a vertex u in a connected, undirected, unweighted graph G isthe maximum distance from u to any other vertex in the graph. That is, if δ(u, v) isthe 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 itsrunning time.(b) What is the asymptotic cost of solving a linear system of equations with n−1 equationsof the formai,ixi+ ai,i+1xi+1= bii = 1, . . . , n − 1and one equation of the forman,1x1+ an,2x2+ ··· + an,nxn= bn(none of the a’s in this equation are zero). The a’s and b’s are given numbers andthe x’s are unknowns. Assume that we use Givens rotations to reduce the coefficientmatrix to a triangular form. Justify your answer.6.006 Final Exam Name 5(c) Suppose a hash function h maps arbitrary keys to values between 0 and m −1, inclu-sive. We hash n keys, k1, k2, . . . , kn. If h(ki) = h(kj), we say that kiand kjcollide.Assuming simple uniform hashing, how should we choose m (in terms of n) such thatthe 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 havingnonnegative weights. Propose an efficient method of finding the shortest path to eachvertex from a single source, and give its running time in terms of n.6.006 Final Exam Name 6Problem 3. Judge Jill [24 points] (3 parts)Judge Jill has created a web site that allows people to file complaints about one another. Eachcomplaint contains exactly two names: that of the person who filed it and that of the person he/sheis complaining about.Jill had hoped to resolve each complaint personally, but the site has received so many complaintsthat 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 beconsistent, not necessarily correct. A labeling is consistent if every complaint labels one personas good and the other person as evil, and no person gets labeled both as good and evil in differentcomplaints.(a) [8 points] Propose a way to model the consistent labeling problem as a graph problem.6.006 Final Exam Name 7(b) [10 points] Propose an efficient algorithm to consistently label all the names as goodor evil, or to decide that no such classification exists. Use the graph model you pro-posed 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 somepeople to figure out who is good and who is evil. She can always determine whether aperson is good or evil by interviewing him or her. Assuming that one person in everycomplaint is good and the other is evil, what is the minimum number of people sheneeds to interview to correctly classify all the people named in the complaints?6.006 Final Exam Name 8Problem 4. Bitdiddle Bins [24 points] (3 parts)Ben Bitdiddle has devised a new data structure called a Bitdiddle Bin. Much like an array or aset, you can INSERT values into it, and you can LOOKUP values to see if they are contained in thestructure. (He’ll figure out DELETE later.)A Bitdiddle Bin is implemented as a pair of lists (arrays), designated the neat list and the messylist, 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 entireBitdiddle Bin.The LOOKUP algorithm for a Bitdiddle Bin is as follows:1. Use binary search to look for the value in the neat list.2. If it wasn’t in the neat list, iterate over the entire messy list to look for the value.The INSERT algorithm is as follows:1. Append the value to the messy list.2. If the messy list is now too big, CLEANUP.This CLEANUP subroutine is run
View Full Document
Unlocking...