” 写作CS270语言、Algorithm程序设计 辅导Homework #4CS270, Fall 2020Due Monday November 2 by 1:00pm PacificGeneral Instructions. The following assignment is meant to be challenging, and we anticipatethat it will take most of you at least 20 hours to complete, so please allow yourself plenty oftime to work on it. We highly recommend reading the entire assignment right away you neverknow when inspiration will Strike. Please provide a formal mathematical proof for all your claims,and present runtime guarantees for your algorithms using asymptotic (big-O//) notation, unlessstated otherwise. You may assume that all basic arithmetic operations (multiplication, subtraction,division, comparison, etc.) take constant time.Collaboration. Please carefully check the collaboration policy on the course website. When indoubt, ask an instructor.Consulting outside Sources. Please carefully check the policy regarding outside sources on thecourse website. Again, when in doubt, ask an instructor.Submission. Homework submission will be through the Gradescope system. Instructions andlinks have been provided through the course website and Piazza. The only accepted format is PDF.Starting with Homework 3, only typed solutions are accepted; we highly recommend producing yoursolutions using LATEX (the text markup language we are also using for this assignment), but otherword processing solutions will also be accepted.Recommended practice problems (do not hand in): KT Problems 7.6, 7.7, 7.9, 7.12, 7.13,7.16, 7.19, 7.22, 7.23, 7.25, 7.27, 7.351Problem 1. (5 points)We saw that what made the Ford-Fulkerson Algorithm for Maximum s-t Flows non-greedy wasthe ability to undo flow by pushing it backwards. This corresponded to sending flow along backwardedges in the residual graph. Using backwards edges seems a little unintuitive, and it is natural toask whether we could avoid Doing so if we are just clever enough with our choice of paths.One answer to this question is Obviously yes. There is a lemma called the Path DecompositionLemma (which was mentioned in Davids class but which you dont need here), which statesthe following: For every s-t flow f, one can (in polynomial time) find s-t paths P1, P2, . . . , Pk (withk m) and corresponding values 1, 2, . . . , k such that PPi:ePii = f(e) for each edge e. Inother words, we can think of flows in terms of the paths along which they send flow. Due to thePath Decomposition Lemma, if we only knew the path decomposition of the maximum s-t flow,we could exactly use those paths Pi with the corresponding amounts i. That is, in iteration i,we would choose that path Pi from s to t, and magically guess to send i units along that path.Unfortunately, this would Require perfect hindsight, i.e., having already computed the maximums-t flow, which is what we want to accomplish in the first place.So a more interesting question is: is there a normal version of the Ford-Fulkerson Algorithmwhich doesnt need perfect hindsight, and still avoids using backwards edges. One candidate mightbe the Edmonds-Karp Algorithm (i.e., choosing specifically the shortest s-t path in the residualgraph in each iteration). After all, for the bad examples we saw in class, it seemed like theproblem was choosing unnecessarily long paths, which we later needed to fix. So we define the lazyEdmonds-Karp Algorithm as the algorithm that always finds a shortest s-t path with availablecapacity, and sends as Much flow as possible along that path. It never considers any backwardsedges, and thus never undoes any flow it sent. The question is now: Does the lazy Edmonds-KarpAlgorithm always find a maximum s-t flow?Prove that this is not the case, by giving a concrete example of one graph with source s and sinkt for which repeatedly pushing flow along only shortest paths will get stuck with a suboptimalflow if no backwards edges are used in the residual graph. Explain what the algorithm does onyour input, what it terminates with, and what the (presumably better) maximum s-t flow wouldbe. Also, prove that your maximum s-t flow is in fact a maximum s-t flow, not just better thanthe one that the lazy Edmonds-Karp Algorithm finds.2Problem 2. (10 points)After the teams success in the previous match against UCLA, you are asked once again to helpthe captain of the USC tennis team arrange a series of matches against UCLAs team. Each teamstill has n players; we index the Trojan players i = 1, . . . , n and the Bruin players j = 1, . . . , n.After the last event, the USC coaches realized that tennis ratings alone were not such greatpredictors of who would win a match. Who would have thought!?! They realized that there aremany additional considerations, such as whether players are right-handed or left-handed, whetherthey play serve-and-volley or baseline, or whether one players trash talk gets under another playersskin, or motivates them more. They ran a huge reconnaissance mission, and now come to you witha complete list of which matches (i, j) the USC player i would win, and which matches the UCLAplayer j would Win. They did this for every pairing (i, j): for each, they can predict who will win.They give you this huge trove of data, and expect you to output a list of matches such that USCwins as many of them as possible.However, there has been another change in the format since the last event: players may nowplay multiple matches, with the following rules: No individual player on either team is allowed to play more than 3 matches. (You canmake them play fewer matches if you want.) Different players may play different numbers ofmatches. No particular match is repeated. That is, for each pair i, j of players, the match i vs. j canbe played at most once.Your goal is now to output a list of matches to play, meeting these conditions, such that USCwins as many of them as possible. Design (and analyze) a polynomial-time algorithm to solve thisproblem.Hint/Note: Since you only have an upper bound on the number of matches played per player,you might as well skip all matches that USC would lose theres no need to play them, since itwont affect How many matches USC wins.3Problem 3. (10 points)You are trying to pick out the classes to take during your computer science major. There are nclasses available, and for each of them, you know how rewarding it would be to take the class. Thatis captured by the integer number ri, which could be positive or negative. (Some classes are notvery rewarding. Of course, CSCI 270 has the largest ri of all of them.) Sometimes, classes buildon each other. While the program does not enforce prerequisites, if you are missing a prerequisitefor a class, you have to spend extra time studying to catch up, which reduces the reward.More specifically, for each pair of classes i, j such that i is a prerequisite for j, you are given aninteger quantity pi,j 0 which gives you the amount of extra studying you will have to do for classj if you didnt also take class i. This pi,j is subtracted from your total reward if you take class jbut not class i. We assume that prerequisites do not contain cycles: if you look at the graph of alledges (i, j) with pi,j 0, this graph contains no cycles.To summarize the preceding discussion: if you take the set S {1, . . . , n} of classes, your totalreward is R(S) := PiSri Pj /S,iSpj,i. We assume that there is no bound on the number ofclasses you are allowed to take.Give (and analyze) a polynomial-time algorithm for finding a set S of classes maximizing R(S).Hint: In addition to the class Material, you might find Section 7.11 in the textbook useful.4Problem 4. (10 points)In proving the Max-Flow/Min-Cut theorem, we saw a first example of what is called a dualitybetween optimization problems. In this problem, we will see another, much simpler, example. Thetwo problems which we will show to be duals are the (undirected) shortest path problem you arefamiliar with (Dijkstra and Bellman/Ford are algorithms that solve it), and a new problem we willdefine here, which we will call the maximum stretch problem. In both problems, your input is anundirected graph G = (V, E) with lengths `e 0 on the edges e E, and a pair of nodes s, t V . In the shortest path problem, your goal is to compute a path of minimum total length froms to t. In the maximum stretch problem, we think of each edge e as a rope of length `e. Our goal isto stretch the graph so that s and t are as far apart from each other as possible; however,none of the ropes can be stretched beyond their length. It is not difficult to see that the bestsolution will put all of the nodes/connections in one dimension. Thus, stated more formally,the goal is to assign a height h(v) R to each node v V , so as to maximize h(t) h(s),while guaranteeing that |h(u) h(v)| `e for each edge e = (u, v) E. To visualize this,think of having little key rings for nodes, and tying pieces of string between nodes of thecorresponding lengths `e. Then you grab the ring for s in one hand, and the ring for t inthe other hand, and try to lift t as far above s as possible without ripping any strings. Thedistance you manage to get between your two hands is the stretch.(a) [4 points]. First, you will prove what is called the weak duality theorem for these twoproblems: that the maximum stretch can be no more than the length of a shortest path s-t path.Specifically, show that the for each feasible height assignment h for G i.e., one satisfying |h(u)h(v)| `e for each edge e = (u, v) E and each s-t path P in G, the s-t stretch h(t) h(s) isno more than the length of the path P. Then, explain why this implies that the maximum possibles-t stretch is no More than the shortest path distance from s to t.Notice that this is in spirit similar to our lemma that the maximum flow is no more than theminimum cut in any graph though your proof techniques will likely be very different, as theseare completely different problems.(b) [5 points]. Next, you will prove what is called the strong duality theorem for these twoproblems: that the maximum stretch is actually equal to the length of the shortest path. Specifically,show that there is a feasible height assignment h for G i.e., one satisfying |h(u) h(v)| `e foreach edge e = (u, v) E such that the stretch h(t)h(s) equals the shortest path distance froms to t.Notice that this is in Spirit similar to our proof of the Max-Flow/Min-Cut Theorem, where weshowed that there is a flow and a cut such that the value of the flow equaled the capacity of thecut. Remember that this showed that the maximum flow equals the minimum cut. Here, you willdo something similar for a different problem.(c) [1 point]. Your answer to part (b) should give you an algorithm for efficiently computinga feasible height assignment maximizing s-t stretch. Argue that a single execution of Dijkstrasalgorithm is all you need to compute the optimal height assignment.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
