1 M482 FALL2020 Midterm II-Take Home NAME(S)___________________________________________. Out: Monday, October 19, 2020 Ret: Monday, November 2, via email, by 6:00PM No extensions or makeups. Please have everything printed. Also please nothing scanned, no pictures of handwritten work. I will not accept any exam submitted after 6:00PM on Monday (answers come cheap and quick when the deadline is past!). 1________ 10 2________ 10 3________ 10 4________ 10 5________ 10 6________ 10 7________ 10 8________ 10 9________ 10 10_______ 10 ∑_______ max 100 points, each problem max 10 points. 2 1. Consider Dijkstra’s algorithm: Initialization Same as MST-Prim, but also define a set S which is the complement of Q Computing loop while Q is nonempty do u € ←Extract-Min(Q) S € ←S € ∪{u} for each v € ∈Adj[u] do Relax(u, v, w) For the directed graph indicated by the sketch on the next page, on exactly which iteration of the while loop is the shortest path distance from the top left vertex with the heavy line to the black vertex at location (5, 2)? Also, compute the shortest path distance to every other vertex in the array. (10 points) Assume that the sequence of arrows shown persists throughout all the vertices, and that each horizontal edge weight is set to exactly 1, each vertical edge weight is set to exactly 2, and each diagonal edge has weight 0. Break ties for Extract-Min lexicographically, for example, (2, 3) would come before (2, 5), if both had the same distance from the source estimate. We are asking at which point the estimate for the distance is the true minimum distance. This is different from asking at which iteration is the black node extracted. Finally, use the algorithm as presented in class, and in Cormen! 3 4 2. Consider the same graph as in problem #1, but without the arrows, yet with the same edge weights. On which iteration of the while loop in Prim’s algorithm would the solid black vertex be extracted? Assume in the initialization that the upper left vertex is the root. Break ties for Extract-Min lexicographically. 5 3A. If the puzzle has no solution, prove it. Otherwise, indicate a solution by using circles for one half solution and rectangles for the other. (5 points) Cube number Opposite pair one Opposite pair two Opposite pair three 1 (6, 11) (7, 12) (2, 8) 2 (2, 4) (2, 7) (2, 8) 3 (3, 11) (3, 7) (1, 5) 4 (4, 12) (4, 7) (4, 8) 5 (2, 7) (3, 4) (5, 7) 6 (10, 7) (6, 12) (4, 6) 7 (3, 9) (7, 11) (3, 11) 8 (6, 12) (10, 12) (8, 8) 9 (2, 9) (1, 11) (1, 11) 10 (7, 10) (6, 10) (4, 10) 11 (5, 9) (1, 7) (5, 6) 12 (5, 9) (1, 5) (7, 7) 6 3B If the puzzle has no solution, prove it, and provide a minimal obstacle. Otherwise, indicate a solution by using circles for one half solution and rectangles for the other. (5 points) Cube number Opposite pair one Opposite pair two Opposite pair three 1 (6, 11) (7, 12) (2, 8) 2 (2, 4) (2, 7) (2, 8) 3 (3, 11) (3, 7) (1, 5) 4 (4, 12) (4, 7) (4, 8) 5 (2, 7) (3, 7) (5, 7) 6 (10, 7) (6, 12) (4, 6) 7 (3, 9) (7, 11) (3, 11) 8 (6, 12) (10, 12) (7, 8) 9 (2, 9) (7, 11) (1, 11) 10 (7, 10) (6, 10) (4, 10) 11 (5, 9) (1, 7) (5, 6) 12 (7, 9) (1, 5) (7, 7) 7 4. Consider the graph in Figure 25.1 in Cormen 3e p. 690. Now add one edge with weight as follows: w(3, 5) = 3. And, change the weight of edge (1, 3) to -8. A For this modified graph, identify a negative weight cycle if one exists. (1 point) B Now take the above modified graph and change the -8 to -6, i.e. have w(1, 3) = -6. For this graph, do the following: Carefully trace Johnson’s algorithm on this modified graph, provided there are no negative weight cycles. If there is one, indicate it; you are done with this problem and #5 below. (9 points) For full credit you must complete all four steps: 1 first draw the original graph with the negative weight edges. Then 2 show the result of running Bellman-Ford from a super sourc. Now 3 show the result after re-weighting edges to remove all negative weight edges. Lastly, 4 report the result of running Dijkstra’s algorithm on all pairs (you need not trace out D’s here) in atlas form. Make sure to report distances from the original graph (before the reweighting process). [This graph is NOT sparse. We only used it to demonstrate the execution of Johnson’s algorithm, not to illustrate the effectiveness of this algorithm on sparse graphs.] 8 5. Trace the Floyd-‐Warshall Algorithm on the graph in problem #4B. This algorithm solves the all-‐pairs shortest path problem but it is not a greedy algorithm. It is a classic example of the dynamic programming technique, which we will cover in depth in the next section of the course. (8 points) For credit, you need to show all the distance (D) matrices as in Fig. 25.4 in Cormen. Finally, suppose that = !!!! , where ! is the nth Catalan number. Which algorithm, Johnson’s or F-‐W, will run faster? Or will they run at the same (asymptotic) speed? Or, are they not comparable? Here we assume there do not exist any negative weight cycles. (2 points) 9 6. Find an example of a (weighted, undirected) graph G(V, E) which has exactly three different MSTs, exactly two different true second-best MSTs, and exactly two true third- best MSTs. If such a graph does not exist, write “impossible.” (10 points) 10 7. Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints. DRAW THE CONSTRAINT GRAPH for credit. If there is no solution, indicate the negative weight cycle in the constraint graph. (10 points) x1 - x7 ≤ 10 x8 - x5 ≤ 3 x1 - x5 ≤ 4 x8 – x7 ≤ 5 x3 – x7 ≤ 4 x6 – x2 ≤ 1 x1 – x6 ≤ 5 x3 – x4 ≤ 4 x4 – x6 ≤ -2 x1 – x2 ≤ 5 x3 – x2 ≤ 2 x7 – x1 ≤ -2 x2 – x7 ≤ 2 x5 – x6 ≤ 0 x6 – x7 ≤ 3 x8 – x1 ≤ 3 x4 – x8 ≤ 2 x7 – x4 ≤ -1 x6 – x3 ≤ -1 x5 – x2 ≤ 1 x3 – x8 ≤ 1 x1 – x8 ≤ 4 x6 – x8 ≤ 0 x2 – x8 ≤ 0 11 8. Consider the 10-edge weighted graph with incidence matrix below: a b c d e f a 1 6 14 5 b 3 7 c 2 13 d 11 e 9 f Determine whether the graph has the following property. Given any two spanning trees, can one tree be transformed into the other by a sequence of edge swaps, where an edge from one is inserted into the other and then an edge is removed from the cycle created, so that the weights of the intermediate trees form a monotone sequence? Return YES, or provide a counterexample. 12 9. Simplest example of II, retaining NP-Completeness The generators below create Instant Insanity-style puzzles constructed from right triangular prisms as described in class. I.e., these “pie slices” are constrained to move only by rotation-no flipping. They have colors on their (three) vertical sides. There are only three positions that a given slice can have relative to the rest of the tower. One can visualize the pie slice with a hole in the center through which a wire passes, preventing the flipping of any slice of the puzzle. (FYI if flipping is allowed, the problem no longer is NP-Complete, and there is a particularly simple criteria for determining if a solution exists.) If an obstacle exists one needs to find the smallest one. As mentioned in class, by obstacle I refer to a subset of the pie slices, which cannot be part of any solution. I.e., any stacking of these slices entails at least one of the three sides having some color showing up two or more times. Write a scratch program to generate the data. I am not asking you to solve/look for min obstacles at this time; I just want you to generate the data correctly. These puzzles are assumed to have 100 slices and each slice has three faces. Therefore the puzzle-coloring scheme is determined by a list of 300 colors. Assume that the colors generated refer to the colors of the slices in the following way. The first three colors will color the bottom slice, slice #1. They will color, in order, the faces as seen from the top of the puzzle, counterclockwise. The next three colors in the list will color the second slice, etc. 1 + ((floor n∙ !!) mod 100), 1 ≤ n ≤ 300, for puzzle one, 1 + ((floor n∙ !!) mod 100), 1 ≤ n ≤ 300, for puzzle two, 1 + ∙ 53 mod 100 , 1 ≤ n ≤ 300, for puzzle three, 1 + ∙ 29 mod 100 , 1 ≤ n ≤ 300, for puzzle four. These formulas specify, exactly, which colors land on which faces, so everyone will have the exact same data set. [Btw the purpose of this exercise is to get you ready for the programming project.] When the project is assigned (shortly) it will be crucial for you to have the correct data. If you run your program with the wrong input, I cannot give any credit. 13 10A. Build a pizza slice problem of fewer than 10 slices that has a minimal obstacle of size = 3. If impossible, say so. (5 points) 14 10B. Build a pizza slice problem of fewer than 10 slices that has a minimal obstacle of size = 5. If impossible, say so. (5 points)
欢迎咨询51作业君
