Introduction to Algorithms
Massachusetts Institute of Technology
Professors , , and
Quiz 2 Solutions Problem 1. True or false [24 points] (8 parts)
Copyright By PowCoder代写 加微信 powcoder
April 13, 2011 6.006 Spring 2011 Quiz 2 Solutions
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.)
Instead of using counting sort to sort digits in the radix sort algorithm, we can use any valid sorting algorithm and radix sort will still sort correctly.
Solution: False. Need stable sort.
The depth of a breadth-first search tree on an undirected graph G = (V, E) from an arbitrary vertex v ∈ V is the diameter of the graph G. (The diameter d of a graph 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 the graph, 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 have depth 1 but the graph has diameter 2.
6.006 Quiz 2 Solutions Name 2
Every directed acyclic graph has exactly one topological ordering.
Solution: False. Some priority constraints may be unspecified, and multiple orderings 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]. As another example, G = (V, E) = ({a, b}, {}) has valid topological orderings [a, b] or [b, c].
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 despite always 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 the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.
6.006 Quiz 2 Solutions Name 3
Dijkstra’s algorithm may not terminate if the graph contains negative-weight edges.
Solution: False. It always terminates after |E| relaxations and |V |+|E| priority queue operations, but may produce incorrect results.
Consider a weighted directed graph G = (V, E, w) and let X be a shortest s-t path for s, t ∈ V . If we double the weight of every edge in the graph, set- ting w′(e) = 2w(e) for each e ∈ E, then X will still be a shortest s-t path in (V, E, w′).
Solution: True. Any linear transformation of all weights maintains all rela- tive path lengths, and thus shortest paths will continue to be shortest paths, and more generally all paths will have the same relative ordering. One simple way of thinking about this is unit conversions between kilometers and miles.
6.006 Quiz 2 Solutions Name 4
If a depth-first search on a directed graph G = (V, E) produces exactly one back edge, then it is possible to choose an edge e ∈ E such that the graph G′ = (V, E − {e}) is acyclic.
Solution: True. Removing the back edge will result in a graph with no back edges, and thus a graph with no cycles (as every graph with at least one cycle has 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 of the cycles that gave rise to the back edge ([a, b, c, a]), but another cycle remains, [a, c, a].
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 to remove 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 5 Problem 2. Short answer [24 points] (6 parts)
(a) What is the running time of RADIX-SORT on an array of n integers in the range 0, 1, . . . , n5 − 1 when using base-10 representation? What is the running time when using a base-n representation?
Solution: Using base 10, each integer has d = log n5 = 5 log n digits. Each COUNTING-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 = logn n5 = 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 no attempt to simplify running times were made (e.g. if running time for base-10 repre- sentation was left as Θ(log10 n5(n + 10))
Common mistakes included substituting n5 as the base instead of 10 or n. This led to Θ(n5) and Θ(n6) runtimes
(b) Whatistherunningtimeofdepth-firstsearch,asafunctionof|V|and|E|,iftheinput graph 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 find all of its neighbors to figure out where to search next. Finding all its neighbors in an adjacency matrix requires O(V ) time, so overall the running time will be O(V 2).
2 points were docked for answers that didn’t give the tightest runtime bound, for ex- ample O(V 2 + E). While technically correct, it was a key point to realize that DFS using 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 positions and edges represent valid moves. What are the in-degree and out-degree of the fol- lowing vertex? (It is O’s turn.)
There were three possible vertices that could have pointed into this board
And 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] ≥ d[u] + w(u, v) (instead of doing so only if d[v] is strictly greater than d[u] + w(u, v)), does the resulting algorithm still produce correct shortest-path weights and a correct shortest-path tree? Justify your answer.
Solution: No. There exists a zero-weight cycle, then it is possible that relaxing an edge will mess up parent pointers so that it is impossible to recreate a path back to the source node. The easiest example is if we had a vertex v that had a zero-weight edge pointing back to itself. If we relax that edge, v’s parent pointer will point back to itself. When we try to recreate a path from some vertex back to the source, if we go through v, we will be stuck there. The shortest-path tree is broken. 1 point was awarded for mentioning that shortest-path weights do get preserved, but also thinking the tree was correct..
6.006 Quiz 2 Solutions Name 7
(e) If you take 6.851, you’ll learn about a priority queue data structure that supports EXTRACT-MIN and DECREASE-KEY on integers in {0, 1, . . . , u − 1} in O(lg lg u) time per operation. What is the resulting running time of Dijkstra’s algorithm on a weighteddirectgraphG=(V,E,w)withedgeweightsin{0,1,…,W −1}?
Solution: The range of integers that this priority queue data structure (van Emde Boas priority queue) will be from 0 to |V |(W −1). This is because the longest possible path will go through |V | edges of weight W −1. Almost the entire class substituted the wrong value for u. Dijkstra’s will call EXTRACT-MIN O(V ) times and DECREASE- KEY O(E) times. In total, the runtime of Dijkstra’s using this new priority queue is O((|V | + |E|) lg lg(|V |w))
2 points were deducted for substituted the wrong u, but understanding how to use the priority queue’s runtimes to get Dijkstra’s runtime
(f) Consider a weighted, directed acyclic graph G = (V, E, w) in which edges that leave the source vertex s may have negative weights and all other edge weights are non- negative. Does Dijkstra’s algorithm correctly compute the shortest-path weight δ(s, t) from s to every vertex t in this graph? Justify your answer.
Solution: Yes, For the correctness of Dijkstra, it is sufficient to show that d[v] = δ(s,v) for every v ∈ V when v is added to s. Given the shortest s Y v path and given that vertex u precedes v on that path, we need to verify that u is in S. If u = s, then certainly u is in S. For all other vertices, we have defined v to be the vertex not in S that is closest to s. Since d[v] = d[u] + w(u, v) and w(u, v) > 0 for all edges except possibly those leaving the source, u must be in S since it is closer to s than v.
It was not sufficient to state that this works because there are no negative weight cycles. Negative weight edges in DAGs can break Dijkstra’s in general, so more justification was needed on why in this case Dijkstra’s works.
6.006 Quiz 2 Solutions Name 8 Problem 3. You are the computer [12 points] (4 parts)
(a) What is the result of relaxing the following edges? 3
Solution: 7, 16, 11 for the new value of the right vertex one point for each edge
(b) Perform a depth-first search on the following graph starting at A. Label every edge in the graph with T if it’s a tree edge, B if it’s a back edge, F if it’s a forward edge, and C if it’s a cross edge. To ensure that your solution will be exactly the same as the staff solution, assume that whenever faced with a decision of which node to pick from a set of nodes, pick the node whose label occurs earliest in the alphabet.
6.006 Quiz 2 Solutions Name
-1 for minor errors in labeling, sometimes resulting from incorrect choice of which node to visit
-2 for major errors in labeling
6.006 Quiz 2 Solutions Name 10
(c) RunDijkstra’salgorithmonthefollowingdirectedgraph,startingatvertexS.Whatis the order in which vertices get removed from the priority queue? What is the resulting shortest-path tree?
3211 S2C3D4E
Dijkstra will visit the vertices in the following order: S, C, A, D, F, E, B.
Dijkstra will relax the edge from D to E before the edge from F to E, since D is closer to S than F is. As a result, the parent of each node is:
-1 for minor errors, such as a missing vertex in the ordering of vertices removed from the priority queue or an incorrect edge in the shortest-path tree
-2 for major errors, such as not providing the shortest-path tree (some people mistak- enly provided the shortest-path length in the tree)
6.006 Quiz 2 Solutions Name
(d) Radix sort the following list of integers in Show the resulting order after each run of
base 10 (smallest at top, largest at bottom). counting sort.
Original list 583 625 682 243 745 522
First sort
Second sort
Third sort
Original 583 625 682 243 745 522
First sort 682 522 583 243 625 745
Second sort 522 625 243 745 682 583
Third sort 243 522 583 625 682 745
-1 for minor errors
-2 for major errors, such
as not using a stable sort for the individual sorts.
6.006 Quiz 2 Solutions Name 12 Problem 4. Burgers would be great right about now [10 points]
Suppose that you want to get from vertex s to vertex t in an unweighted graph G = (V, E), but you would like to stop by vertex u if it is possible to do so without increasing the length of your path by more than a factor of α.
Describe an efficient algorithm that would determine an optimal s-t path given your preference for stopping at u along the way if doing so is not prohibitively costly. (It should either return the shortest path from s to t or the shortest path from s to t containing u, depending on the situation.)
If it helps, imagine that there are burgers at u.
Solution: Since the graph is unweighted, one can use BFS for the shortest paths computation. We run BFS twice, once from s and once from u. The shortest path from s to t containing u is composed of the shortest path from s to u and the shortest path from u to t. We can now compare the length of this path to the length of the shortest path from s to t, and choose the one to return based on their lengths. The total running time is O(V + E).
An alternative is to use Dijkstra algorithm. This works, but the algorithm becomes slower. Same for Bellman-Ford.
6.006 Quiz 2 Solutions Name 13 Problem 5. How I met your midterm [10 points]
Ted and Marshall are taking a roadtrip from Somerville to Vancouver (that’s in Canada). Because it’s a 52-hour drive, Ted and Marshall decide to switch off driving at each rest stop they visit; however, because Ted has a better sense of direction than Marshall, he should be driving both when they depart and when they arrive (to navigate the city streets).
Given a route map represented as a weighted undirected graph G = (V, E, w) with positive edge weights, where vertices represent rest stops and edges represent routes between rest stops, devise an efficient algorithm to find a route (if possible) of minimum distance between Somerville and Vancouver such that Ted and Marshall alternate edges and Ted drives the first and last edge.
Solution: There are two correct and efficient ways to solve this problem. The first solution makes a new graph G′. For every vertex u in G, there are two vertices uM and uT in G′: these represent reaching the rest stop u when Marshall (for uM ) or Ted (for uT ) will drive next. For every edge (u,v)inG,therearetwoedgesinG′: (uM,vT)and(uT,vM). Bothoftheseedgeshavethesame weight as the original.
We run Dijkstra’s algorithm on this new graph to find the shortest path from SomervilleT to VancouverM (since Ted drives to Vancouver, Marshall would drive next if they continued). This guarantees that we find a path where Ted and Marshall alternate, and Ted drives the first and last segment. Constructing this graph takes linear time, and running Dijkstra’s algorithm on it takes O(V log V + E) time with a Fibonacci heap (it’s just a constant factor worse than running Dijkstra on the original graph).
The second correct solution is equivalent to the first, but instead of modifying the graph, we mod- ify Dijkstra’s algorithm. Dijkstra’s algorithm will store two minimum distances and two parent pointers for each vertex u: the minimum distance dodd using an odd number of edges, and the minimum distance deven using an even number of edges, along with their parent pointers πodd and πeven. (These correspond to the minimum distance and parent pointers for uT and uM in the previ- ous solution). In addition, we put each vertex in the priority queue twice: once with dodd as its key, and once with deven as its key (this corresponds to putting both uT and uM in the priority queue in the previous solution).
When we relax edges in the modified version of Dijkstra, we check whether v.dodd > u.deven + w(u, v), and vice versa. One important detail is that we need to initialize Somerville.dodd to ∞, not 0. This algorithm has the same running time as the previous one.
A correct but less efficient algorithm used Dijkstra, but modified it to traverse two edges at a time on every step except the first, to guarantee a path with an odd number of edges was found. Many students incorrectly claimed this had the same running time as Dijkstra’s algorithm; however, computing all the paths of length 2 (this is the square of the graph G) actually takes a total of O(V E) time, whether you compute it beforehand or compute it for each vertex when you remove it from Dijkstra’s priority queue. This solution got 5 points.
The most common mistake on the problem was to augment Dijkstra (or Bellman-Ford) by keeping track of either the shortest path’s edge count for each vertex, or the parity of the number edges in
6.006 Quiz 2 Solutions Name 14
the shortest path. This is insufficient to guarantee that the shortest odd-edge-length path is found, and this solution got 2 points. Here is an example of a graph where the algorithm fails: once the odd-edge-count path of weight 1 to A is found, Dijkstra will ignore the even-edge-count path of weight 4 to A since it has greater weight. As a result, the odd-edge-count path to V will be missed entirely.
Another common mistake was to use Dijkstra, and if the path Dijkstra found had an even number of edges, to attempt to add or remove edges until a path with an odd number of edges was obtained. In general, there is no guarantee the shortest path with an odd number of edges is at all related to the shortest path with an even number of edges.
Some algorithms ran Dijkstra, and if Dijkstra found a path with an even number of edges, removed some edge or edges from the graph and re-ran Dijkstra. This algorithm fails on the following graph, where the shortest path with an odd number of edges uses all the edges and vertices (note that we visit A twice; the first time, Ted drives to A, and the second time, Marshall drives to A):
One last common mistake was to attempt to use Breadth-First Search to label each vertex as an odd or even number of edges from Somerville (or sometimes to label them as odd, even, or both). This does not help: the smallest-weight path with an odd number of edges could go through any particular vertex after having traversed an odd or even number of edges, and BFS will not correctly predict which. These solutions got 0 points.
Algorithms which returned the correct answer but with exponential running time got at most 2 points.
6.006 Quiz 2 Solutions Name 15 Problem 6. Just reverse the polarity already [10 points]
Professor Kirk has managed to get himself lost in his brand new starship. Furthermore, while boldly going places and meeting strange new, oddly humanoid aliens, his starship’s engines have developed a strange problem: he can only make “transwarp jump” to solar systems at distance exactly 5 from his location.
Given a starmap represented as an unweighted undirected graph G = (V, E), where vertices repre- sent glorious new solar systems to explore and edges represent transwarp routes, devise an efficient algorithm to find a route (if possible) of minimum distance from Kirk’s current location s to the location t representing Earth, that Kirk’s ship will be able to follow. Please hurry—Professor Kirk doesn’t want to miss his hot stardate!
Solution: In general, the idea is to convert G = (V, E) into a graph G′ = (V, E′) representing all the feasible transwarp jumps that Kirk can make, i.e., with an edge (u, v) if there is a simple path in G from u to v of length exactly 5. (Note that this definition is the notion of “distance” in the problem, as clarified during the quiz.) Once we have such a graph G′, we simply run breadth-first search on G′ from s, and follow parent pointers from t to recover the shortest route (if there one) for Kirk to follow. The running time of this breadth-first search is O(V + E′) = O(V 2).
The central question is how to compute G′. The best solutions we know run in O(V 3) time. There are two ways to achieve this bound.
The first O(V 3) algorithm is a modification of breadth-first search from every vertex. For each vertex v, we construct the set N1(v) of all neighbors of v. Next we construct the set N2(v) of all vertices reachable by a path of length 2 from v, by taking the union of N1(u) for each u ∈ N1(v). Then we construct N3(v), N4(v), and N5(v) similarly. Constructing N1(v) costs O(V ) time, while constructing Nk(v) for k ∈ {2, 3, 4, 5} costs O(v2) ti
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com