代做CS270语言、Algorithm程序设计代写、代做c++，Python编程

日期：2020-11-01 11:24

Homework #4

CS270, Fall 2020

Due Monday November 2 by 1:00pm Pacific

General Instructions. The following assignment is meant to be challenging, and we anticipate

that it will take most of you at least 20 hours to complete, so please allow yourself plenty of

time to work on it. We highly recommend reading the entire assignment right away — you never

know 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, unless

stated 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 in

doubt, ask an instructor.

Consulting outside sources. Please carefully check the policy regarding outside sources on the

course website. Again, when in doubt, ask an instructor.

Submission. Homework submission will be through the Gradescope system. Instructions and

links 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 your

solutions using LATEX (the text markup language we are also using for this assignment), but other

word 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.35

1

Problem 1. (5 points)

We saw that what made the Ford-Fulkerson Algorithm for Maximum s-t Flows non-greedy was

the ability to undo flow by pushing it backwards. This corresponded to sending flow along backward

edges in the residual graph. Using backwards edges seems a little unintuitive, and it is natural to

ask 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 Decomposition

Lemma (which was mentioned in David’s class — but which you don’t need here), which states

the following: For every s-t flow f, one can (in polynomial time) find s-t paths P1, P2, . . . , Pk (with

k ≤ m) and corresponding values α1, α2, . . . , αk such that P

Pi:e∈Pi

αi = f(e) for each edge e. In

other words, we can think of flows in terms of the paths along which they send flow. Due to the

Path 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 maximum

s-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 Algorithm

which doesn’t need perfect hindsight, and still avoids using backwards edges. One candidate might

be the Edmonds-Karp Algorithm (i.e., choosing specifically the shortest s-t path in the residual

graph in each iteration). After all, for the bad examples we saw in class, it seemed like the

problem was choosing unnecessarily long paths, which we later needed to fix. So we define the “lazy

Edmonds-Karp Algorithm” as the algorithm that always finds a shortest s-t path with available

capacity, and sends as much flow as possible along that path. It never considers any backwards

edges, and thus never undoes any flow it sent. The question is now: Does the lazy Edmonds-Karp

Algorithm 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 sink

t for which repeatedly pushing flow along only shortest paths will get “stuck” with a suboptimal

flow if no backwards edges are used in the residual graph. Explain what the algorithm does on

your input, what it terminates with, and what the (presumably better) maximum s-t flow would

be. Also, prove that your “maximum s-t flow” is in fact a maximum s-t flow, not just better than

the one that the “lazy Edmonds-Karp Algorithm” finds.

2

Problem 2. (10 points)

After the team’s success in the previous match against UCLA, you are asked once again to help

the captain of the USC tennis team arrange a series of matches against UCLA’s team. Each team

still 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 great

predictors of who would win a match. Who would have thought!?! They realized that there are

many additional considerations, such as whether players are right-handed or left-handed, whether

they play serve-and-volley or baseline, or whether one player’s trash talk gets under another player’s

skin, or motivates them more. They ran a huge reconnaissance mission, and now come to you with

a complete list of which matches (i, j) the USC player i would win, and which matches the UCLA

player 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 USC

wins as many of them as possible.

However, there has been another change in the format since the last event: players may now

play multiple matches, with the following rules:

? No individual player on either team is allowed to play more than 3 matches. (You can

make them play fewer matches if you want.) Different players may play different numbers of

matches.

? No particular match is repeated. That is, for each pair i, j of players, the match i vs. j can

be played at most once.

Your goal is now to output a list of matches to play, meeting these conditions, such that USC

wins as many of them as possible. Design (and analyze) a polynomial-time algorithm to solve this

problem.

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 — there’s no need to play them, since it

won’t affect how many matches USC wins.

3

Problem 3. (10 points)

You are trying to pick out the classes to take during your computer science major. There are n

classes available, and for each of them, you know how rewarding it would be to take the class. That

is captured by the integer number ri

, which could be positive or negative. (Some classes are not

very rewarding. Of course, CSCI 270 has the largest ri of all of them.) Sometimes, classes build

on each other. While the program does not enforce prerequisites, if you are missing a prerequisite

for 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 an

integer quantity pi,j > 0 which gives you the amount of extra studying you will have to do for class

j if you didn’t also take class i. This pi,j is subtracted from your total reward if you take class j

but not class i. We assume that prerequisites do not contain cycles: if you look at the graph of all

edges (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 total

reward is R(S) := Pi∈Sri ?Pj /∈S,i∈S

pj,i. We assume that there is no bound on the number of

classes 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.

4

Problem 4. (10 points)

In proving the Max-Flow/Min-Cut theorem, we saw a first example of what is called a duality

between optimization problems. In this problem, we will see another, much simpler, example. The

two problems which we will show to be duals are the (undirected) shortest path problem you are

familiar with (Dijkstra and Bellman/Ford are algorithms that solve it), and a new problem we will

define here, which we will call the maximum stretch problem. In both problems, your input is an

undirected 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 from

s to t.

? In the maximum stretch problem, we think of each edge e as a rope of length `e. Our goal is

to “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 best

solution 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 the

corresponding lengths `e. Then you grab the ring for s in one hand, and the ring for t in

the other hand, and try to lift t as far above s as possible without ripping any strings. The

distance 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 two

problems: 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) is

no more than the length of the path P. Then, explain why this implies that the maximum possible

s-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 the

minimum cut in any graph — though your proof techniques will likely be very different, as these

are completely different problems.

(b) [5 points]. Next, you will prove what is called the “strong duality” theorem for these two

problems: 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 for

each edge e = (u, v) ∈ E — such that the stretch h(t)?h(s) equals the shortest path distance from

s to t.

Notice that this is in spirit similar to our proof of the Max-Flow/Min-Cut Theorem, where we

showed that there is a flow and a cut such that the value of the flow equaled the capacity of the

cut. Remember that this showed that the maximum flow equals the minimum cut. Here, you will

do something similar for a different problem.

(c) [1 point]. Your answer to part (b) should give you an algorithm for efficiently computing

a feasible height assignment maximizing s-t stretch. Argue that a single execution of Dijkstra’s

algorithm is all you need to compute the optimal height assignment.

5