Introduction to Algorithms November 17, 2010Massachusetts Institute of Technology 6.006 Fall 2010Professors Konstantinos Daskalakis and Patrick Jaillet Quiz 2Quiz 2• 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 120 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 is closed book. You may use two 81200× 1100or A4 crib sheet (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.• When writing an algorithm, a clear description in English will suffice. Pseudo-code is notrequired.• When asked for an algorithm, your algorithm should have the time complexity specified inthe problem with a correct analysis. If you cannot find such an algorithm, you will generallyreceive partial credit for a slower algorithm if you analyze your algorithm correctly.• 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. This quiz is shorterthan the first, so we expect you to take the time to write clear and thorough solutions.• Good luck!Problem Parts Points Grade Grader1 2 22 4 383 2 204 1 205 3 206 1 20Total 120Name:FridayRecitation:Aleksander11 AMArnab12 PMAlina3 PMMatthew4 PM6.006 Quiz 2 Name 2Problem 1. What is Your Name? [2 points] (2 parts)(a) [1 point] Flip back to the cover page. Write your name there.(b) [1 point] Flip back to the cover page. Circle your recitation section.6.006 Quiz 2 Name 3Problem 2. Short Answer [38 points] (4 parts)(a) [9 points] Give an example of a graph such that running Dijkstra on it would giveincorrect distances.(b) [9 points] Give an efficient algorithm to sort n dates (represented as month-day-yearand all from the 20thcentury), and analyze the running time.6.006 Quiz 2 Name 4(c) [10 points] Give an O(V + E)-time algorithm to remove all the cycles in a directedgraph G = (V, E). Removing a cycle means removing an edge of the cycle. If thereare k cycles in G, the algorithm should only remove O(k) edges.(d) [10 points] Let G = (V, E) be a weighted, directed graph with exactly one negative-weight edge and no negative-weight cycles. Give an algorithm to find the shortestdistance from s to all other vertices in V that has the same running time as Dijkstra.6.006 Quiz 2 Name 5Problem 3. Path Problems [20 points] (2 parts)We are given a directed graph G = (V, E), and, for each edge (u, v) ∈ E, we are given a proba-bility f(u, v) that the edge may fail. These probabilities are independent. The reliability π(p) of apath p = (u1, u2, . . . uk) is the probability that no edge fails in the path, i.e.π(p) = (1 − f (u1, u2)) · (1 − f (u2, u3)) . . . · (1 − f (uk−1, uk)). Given a graph G, the edge failureprobabilities, and two vertices s, t ∈ V , we are interested in finding a path from s to t of maximumreliability.(a) [10 points] Propose an efficient algorithm to solve this problem. Analyze its runningtime.(b) [10 points] You tend to be risk-averse and in addition to finding a most reliable simplepath from s to t, you also want to find a next-most reliable simple path, and outputthese two paths. Propose an algorithm to solve the problem, argue its correctness, andgive its asymptotic running time.6.006 Quiz 2 Name 6Problem 4. Flight Plans [20 points]When an airline is compiling flight plans to all destinations from an airport it serves, the flightplans are plotted through the air over other airports in case the plane needs to make an emergencylanding. In other words, flights can be taken only along pre-defined edges between airports. Twoairports are adjacent if there is an edge between them. The airline also likes to ensure that all theairports along a flight plan will be no more than three edges away from an airport that the airlineregularly serves.Given a graph with V vertices representing all the airports, the subset W of V which are served bythe airline, the distance w(u, v) for each pair of adjacent airports u, v, and a base airport s, give analgorithm which finds the shortest distance from s to all other airports, with the airports along thepath never more than 3 edges from an airport in W .6.006 Quiz 2 Name 7Problem 5. Tree Searches [20 points] (3 parts)In this problem we consider doing a depth first search of a perfect binary search tree B. In a perfectbinary search tree a node p can have either 2 or 0 children (but not just one child) with the usualrequirement that any node in the left subtree of p is less than p and node in the right subtree isgreater than p. In addition, all nodes with no children (leaves) must be at the same level of thetree. To make B into a directed graph, we consider the nodes of B to be the vertices of the graph.For each node p, we draw a directed edge from p to its left child and from p to its right child. Anexample of a perfect binary search tree represented as a graph is shown in Figure 1.7594 6 810Figure 1: An example of a perfect binary search tree represented as a directed graph.(a) [6 points] We structure our adjacency function such that at a node p, we first runDFS-VISIT on the left child of p and then on the right child. When we have finishedexpanding a node (i.e. just before we return from DFS-VISIT), we print the node.What is the first node printed? What is the last node printed? Give a short defense ofyour answer.6.006 Quiz 2 Name 8(b) [7 points] Does DFS print out the nodes of the tree in increasing or decreasing order?If yes, give a proof. If no, give a small counter example where the algorithm fails toprint out the nodes in increasing or decreasing order and show the output of DFS onyour example.(c) [7 points] Recall that usually when doing depth first search, we use the parent struc-ture to keep track of which vertices have been visited. During the search, if a vertexv is in parent, the search will not run DFS-VISIT(v) again. Aspen Tu declares thatparent is unnecessary when doing a DFS of B.
View Full Document
Unlocking...