Introduction to Analysis of Algorithms October 15, 2020 Boston University CS 330 Professor Adam Smith, Dora Erdos Fall 2020 Homework 7 Early deadline: Wednesday, October 21 at 11:59 PM No penalty later deadline: Saturday, October 24 at 11:59 PM Homework Guidelines Collaboration policy Collaboration on homework problems, with the exception of programming assignments and reading quizzes, is permitted, but not encouraged. If you choose to collaborate on some problems, you are allowed to discuss each problem with at most 5 other students currently enrolled in the class. Before working with others on a problem, you should think about it yourself for at least 45 minutes. Finding answers to problems on the Web or from other outside sources (these include anyone not enrolled in the class) is strictly forbidden. You must write up each problem solution by yourself without assistance, even if you collaborate with others to solve the problem. You must also identify your collaborators. If you did not work with anyone, you should write ”Collaborators: none.” It is a violation of this policy to submit a problem solution that you cannot orally explain to an instructor or TA. Solution guidelines For problems that require you to provide an algorithm, you must give the following: 1. a precise description of the algorithm in English and, if helpful, pseudocode, 2. a proof of correctness, 3. an analysis of running time and space. You may use algorithms from class as subroutines. You may also use any facts that we proved in class. You should be as clear and concise as possible in your write-up of solutions. A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand. Points might be subtracted for illegible handwriting and for solutions that are too long. Incorrect solutions will get from 0 to 30% of the grade, depending on how far they are from a working solution. Correct solutions with possibly minor flaws will get 70 to 100%, depending on the flaws and clarity of the write up. Exercises (do not hand in) The following exercises are meant for practicing using the cut and cycle properties. • Given an edge e in the MST of a graph G, find and output a cut S for which it is the lightest edge in the cutset. • Given an edge e not in the MST, find and output a cycle C on which it is the heaviest edge. 1 # I CS330_AHW7 1 of 3 Homework problems to hand in 1. (MST Updates) Suppose you are given a graph G (with unique edge weights) and its associated minimum spanning tree M , along with an edge (u, v) 2 G that we want to remove. Call the resulting graph with the edge removed G0. Assume that G0 is still connected. (a) Argue that it’s su cient to change at most one edge in the MST for G so that it’s the MST for G0. How do the cycle and cut properties help you find the edge to change? Hint: Think about two cases separately: (u, v) 2M and (u, v) /2M . (b) Write an algorithm that takes G, the MST of G, and an edge e in G, and outputs the minimum spanning tree of G0 (again, assuming G0 is still connected). Your algorithm should run in O(n+m) time (do not recompute the MST from scratch; instead modify the MST you are given). Below are some examples of graphs with MST edges labeled, and the resulting G0 and MST of G0 2. (Maximum clearance routes) Every year, trucks get stuck on Storrow Drive because of the low bridges (sometimes called “storrowing”). Suppose you’re running a trucking company in Boston with n warehouses. Each section of road e 2 E will be annotated with the clearance of the lowest bridge on that portion of road ce. Assume all of the roads are undirected, and that all of the clearances are unique. We’ll say that the clearance of a route from i to j is the minimum clearance of all the road segments on the route (you can’t drive a truck that’s taller than the lowest bridge on the route). Next, we’ll say that a route is a maximum-clearance route between i and j if it is the route between i and j with largest route clearance out of 2 CS330_AHW7 2 of 3 all possible routes from i to j. Intuitively, the maximum-clearance route between two nodes tells you the tallest truck that you can drive between the two locations without getting stuck under a bridge, as well as which path to use. You want to find an algorithm that computes a tree for max-clearance routes from a given node s. After giving it some thought, you think it might be related to the idea of a maximum spanning tree with respect to the edge clearances. Note: the maximum spanning tree of a graph G is just a tree that connects all vertices in G (hence ”spanning”) while maximizing the sum of the edge weights in the tree. Cycles are not allowed, as we still want a tree. (a) State the cut and cycle property for maximum spanning trees (MaxST). (b) Show that in any graph G with unique edge clearances, the path given by using edges from the maximum spanning tree of G (with respect to the edge weights given by the clearances ce) gives the maximum clearance route between any two warehouses. [Hint: There are a couple of natural ways to do this. One way is to proceed by contradiction: suppose that the highest-clearance path is not part of the MaxST; show that together with edges in the MaxST it creates a cycle that contradicts the cycle property above.] (c) Give a polynomial-time algorithm that takes a graph G with distinct edge clearances and outputs the maximum spanning tree. Hint: Modify any of the minimum-weight spanning tree algorithms from class. 3 CS330_AHW7 3 of 3 欢迎咨询51作业君
