Introduction to Algorithms April 16, 2008Massachusetts Institute of Technology 6.006 Spring 2008Professors Srini Devadas and Erik Demaine Quiz 2Quiz 2• 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 5 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 7 352 2 203 2 204 1 205 1 25Total 120Name:Circle your recitation time:Hueihan Jhuang: (10AM) (11AM) Victor Costan (2PM) (3PM)6.006 Quiz 2 Name 2Problem 1. True or False [35 points] (7 parts)Decide whether these statements are True or False. You must briefly justify all your answers toreceive full credit.(a) To sort n integers in the range from 1 to n2, a good implementation of radix sort isasymptotically faster in the worst case than any comparison sort.True FalseExplain:(b) Call an ordered pair (x1, y1) of numbers lexically less than an ordered pair (x2, y2)if either (i) x1< x2or (ii) x1= x2and y1< y2. Then a set of ordered pairs canbe sorted lexically by two passes of a sorting algorithm that only compares individualnumbers.True FalseExplain:6.006 Quiz 2 Name 3(c) Any in-place sorting algorithm can be used as the auxiliary sort in radix sort.True FalseExplain:(d) Every directed acyclic graph has only one topological ordering of its vertices.True FalseExplain:(e) If the priority queue in Dijkstra’s algorithm is implemented using a sorted linked list(where the list is kept sorted after each priority queue operation), then Dijkstra’s algo-rithm would run in O(E lg V + V lg V ) time.True FalseExplain:6.006 Quiz 2 Name 4(f) In searching for a shortest path from vertex s to vertex t in a graph, two-way breadth-first search never visits more nodes than a normal one-way breadth-first search.True FalseExplain:(g) Every sorting algorithm requires Ω(n lg n) comparisons in the worst case to sort nelements.True FalseExplain:6.006 Quiz 2 Name 5Problem 2. Linear Dijkstra? [20 points] (2 parts)(a) Professor Devamaine has just invented an exciting optimization for Dijkstra’s algo-rithm that runs in O(V + E) time for undirected graphs with edge weights of just 0and 1.Show the professor that the same time bound can be achieved simply by modifyingthe graph and then running breadth-first search as a black box.6.006 Quiz 2 Name 6(b) After hearing of his colleague’s embarrassment, Professor Demaidas invents anothermodification to Dijkstra’s algorithm that runs in O(V + E) time for undirected graphswith edge weights of just 1 and 2.Show the professor that the same time bound can again be achieved by modifying thegraph and then running breadth-first search as a black box.6.006 Quiz 2 Name 7Problem 3. Bottleneck Path [20 points] (2 parts)(a) In the bottleneck-path problem, you are given a graph G with edge weights, twovertices s and t, and a particular weight W ; your goal is to find a path from s to t inwhich every edge has at least weight W . Describe an efficient algorithm to solve thisproblem. Your algorithm should work even if the edge weights are negative and/or theparticular weight W is negative.6.006 Quiz 2 Name 8(b) In the maximum-bottleneck-path problem, you are given a graph G with edge weights,and two vertices s and t; your goal is to find a path from s to t whose minimum edgeweight is maximized. Describe an efficient algorithm to solve this problem that usesan efficient algorithm from Part (a) as a subroutine. You may assume an efficientalgorithm for Part (a) exists, and use it as a black box.6.006 Quiz 2 Name 9Problem 4. Reality [20 points]You’ve just agreed to star in the new hit reality show, Whose Geek Is It Anyway? At the outset,you’re given a map of an island of puzzles, which is a directed graph marked with a start vertex sand a goal vertex t. Traversing each edge e requires solving a puzzle, which you believe you cansolve with probability p(e). Describe how to modify the graph so that Dijkstra’s algorithm willfind a path from s to t that has the maximum probability of winning. (Assume your abilities tosolve different puzzles are independent events.)A sample input:s t85%90%60%99%95%80%50%30%45%40%65%25%(home) (fame, fortune)6.006 Quiz 2 Name 10Problem 5. Negative-Weight Cycles [25 points]If a directed graph G = (V, E) contains a negative-weight cycle, shortest paths to some verticeswill not exist, but there may still be shortest paths to other vertices. Assume that every vertex vis reachable from the source vertex s in G. Give an efficient algorithm that labels each vertex vwith the shortest-path distance from s to v, or with −∞ if no shortest path exists. (In other words,compute δ(s, v) for all v.) You can invoke all algorithms covered in lectures or recitations.For reference, below is the pseudocode for Bellman Ford adapted from CLRS, which returns Falseif there are reachable negative weight cycles and True otherwise:def bellman_ford(V, E, w, s):1 initialize_single_source(V, E, s)2 for i in range(|V|-1):3 for (u, v) in E:4 relax(u, v, w)5 for (u, v) in E:6 if d[v] > d[u] + w(u, v):7 return False8 return TrueSCRATCH PAPERSCRATCH
View Full Document
Unlocking...