Introduction to Algorithms April 13, 2011Massachusetts Institute of Technology 6.006 Spring 2011Professors Erik Demaine, Piotr Indyk, and Manolis Kellis Quiz 2 SolutionsQuiz 2 SolutionsProblem 1. True or false [24 points] (8 parts)For each of the following questions, circle either T (True) or F (False). Explain your choice.(Your explanation is worth more than your choice of true or false.)(a) T F Instead of using counting sort to sort digits in the radix sort algorithm, we canuse any valid sorting algorithm and radix sort will still sort correctly.Solution: False. Need stable sort.(b) T F The depth of a breadth-first search tree on an undirected graph G = (V, E) froman arbitrary vertex v ∈ V is the diameter of the graph G. (The diameter d of agraph is the smallest d such that every pair of vertices s and t have δ(s, t) ≤ d.)Solution: False. An arbitrary vertex could lay closer to the ’center’ of thegraph, hence the BFS depth will be underestimating the diameter. For exam-ple, in graph G = (V, E) = ({a, v, b}, {(a, v), (v, b)}), a BFS from v will havedepth 1 but the graph has diameter 2.6.006 Quiz 2 Solutions Name 2(c) T F Every directed acyclic graph has exactly one topological ordering.Solution: False. Some priority constraints may be unspecified, and multipleorderings may be possible for a given DAG. For example a graph G = (V, E) =({a, b, c}, {(a, b), (a, c)}) has valid topological orderings [a, b, c] or [a, c, b]. Asanother example, G = (V, E) = ({a, b}, {}) has valid topological orderings [a, b]or [b, c].(d) T F Given a graph G = (V, E) with positive edge weights, the Bellman-Ford algo-rithm and Dijkstra’s algorithm can produce different shortest-path trees despitealways producing the same shortest-path weights.Solution: True. Both algorithms are guaranteed to produce the same shortest-path weight, but if there are multiple shortest paths, Dijkstra’s will choose theshortest path according to the greedy strategy, and Bellman-Ford will choose theshortest path depending on the order of relaxations, and the two shortest pathtrees may be different.6.006 Quiz 2 Solutions Name 3(e) T F Dijkstra’s algorithm may not terminate if the graph contains negative-weightedges.Solution: False. It always terminates after |E| relaxations and |V |+|E| priorityqueue operations, but may produce incorrect results.(f) T F Consider a weighted directed graph G = (V, E, w) and let X be a shortest s-tpath for s, t ∈ V . If we double the weight of every edge in the graph, set-ting w0(e) = 2w(e) for each e ∈ E, then X will still be a shortest s-t path in(V, E, w0).Solution: True. Any linear transformation of all weights maintains all rela-tive path lengths, and thus shortest paths will continue to be shortest paths, andmore generally all paths will have the same relative ordering. One simple way ofthinking about this is unit conversions between kilometers and miles.6.006 Quiz 2 Solutions Name 4(g) T F If a depth-first search on a directed graph G = (V, E) produces exactly one backedge, then it is possible to choose an edge e ∈ E such that the graph G0=(V, E − {e}) is acyclic.Solution: True. Removing the back edge will result in a graph with no backedges, and thus a graph with no cycles (as every graph with at least one cyclehas at least one back edge). Notice that a graph can have two cycles but a sin-gle back edge, thus removing some edge that disrupts that cycle is insufficient,you have to remove specifically the back edge. For example, in graph G =(V, E) = ({a, b, c}, {(a, b), (b, c), (a, c), (c, a)}), there are two cycles [a, b, c, a]and [a, c, a], but only one back edge (c, a). Removing edge (b, c) disrupts one ofthe cycles that gave rise to the back edge ([a, b, c, a]), but another cycle remains,[a, c, a].(h) T F If a directed graph G is cyclic but can be made acyclic by removing one edge,then a depth-first search in G will encounter exactly one back edge.Solution: False. You can have multiple back edges, yet it can be possible toremove one edge that destroys all cycles. For example, in graph G = (V, E) =({a, b, c}, {(a, b), (b, c), (b, a), (c, a)}), there are two cycles ([a, b, a] and [a, b, c, a])and a DFS from a in G returns two back edges ((b, a) and (c, a)), but a single re-moval of edge (a, b) can disrupt both cycles, making the resulting graph acyclic.6.006 Quiz 2 Solutions Name 5Problem 2. Short answer [24 points] (6 parts)(a) What is the running time of RADIX-SORT on an array of n integers in the range0, 1, . . . , n5− 1 when using base-10 representation? What is the running time whenusing a base-n representation?Solution: Using base 10, each integer has d = log n5= 5 log n digits. EachCOUNTING-SORT call takes Θ(n + 10) = Θ(n) time, so the running time of RADIX-SORT is Θ(nd) = Θ(n log n).Using base n, each integer has d = lognn5= 5 digits, so the running time of RADIX-SORT is Θ(5n) = Θ(n).2 points were awarded for correct answers on each part. A point was deducted if noattempt to simplify running times were made (e.g. if running time for base-10 repre-sentation was left as Θ(log10n5(n + 10))Common mistakes included substituting n5as the base instead of 10 or n. This led toΘ(n5) and Θ(n6) runtimes(b) What is the running time of depth-first search, as a function of |V | and |E|, if the inputgraph is represented by an adjacency matrix instead of an adjacency list?Solution: DFS visits each vertex once and as it visits each vertex, we need to findall of its neighbors to figure out where to search next. Finding all its neighbors in anadjacency matrix requires O(V ) time, so overall the running time will be O(V2).2 points were docked for answers that didn’t give the tightest runtime bound, for ex-ample O(V2+ E). While technically correct, it was a key point to realize that DFSusing an adjacency matrix doesn’t depend on the number of edges in the graph.6.006 Quiz 2 Solutions Name 6(c) Consider the directed graph where vertices are reachable tic-tac-toe board positionsand edges represent valid moves. What are the in-degree and out-degree of the fol-lowing vertex? (It is O’s turn.)X O XOXSolution: There were three possible vertices that could have pointed into this boardposition:O XOXX OOXX O XOAnd there are four possible vertices that could have pointed out from this board posi-tion as O has four spaces to move to. In-degree is 3, out-degree is 4.(d) If we modify the RELAX portion of the Bellman-Ford algorithm so that it updates d[v]and π[v] if d[v] ≥
View Full Document
Unlocking...