xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

无代写-CSC 226

时间：2021-03-07

CSC 226: Problem Set 3

Problem Set 3

Network Flows and Probability

Due: 11:55pm Thursday, March 18, 2021

1 Min-Cut and increasing all edge capacities by 1 (10 marks)

A friend makes the following claim: “Let G be an arbitrary flow network and let

(A∗, B∗) be a minimum s-t cut. Now, let’s increase the capacity of each edge by 1.

Then (A∗, B∗) must still be minimum s-t cut.”

Is the friend right? Explain why or why not.

2 Max-Flow with Node Capacities (10 marks)

In a standard Max-Flow problem, we assume that edges have capacities, and there

is no explicit limit on how much flow is allowed to pass through a node. We now

consider a variant of the standard problem where nodes, not edges, have capacities.

Let G = (V,E) be a directed graph, with source s ∈ V , sink t ∈ V , and nonnegative

node capacities cv for each v ∈ V . Given a flow f in this graph, the flow through

a node v is defined as f in(v). We call a flow feasible if it satisfies the usual flow-

conservation constraints and the node-capacity constraints: f in(v) ≤ cv for all nodes.

Show how the Ford-Fulkerson algorithm can be used to find a maximum s-t flow in

such a node-capacitated network.

3 Tragic Comedy and Network Flows (10 marks)

A ship full of k comedians and 2k ordinary (non-comedian) people is capsizing. The

hope is to evacuate all people onboard via rescue boats. Fortunately, each comedian

has one rescue boat (in case they had to escape a tough crowd), and each boat can

carry two additional passengers (for a total of one comedian and two non-comedians).

Therefore, if the non-comedians could be arbitrarily paired up and each pair could

go on one comedian’s boat, everyone could be evacuated.

However, certain ordinary people so strongly dislike the jokes of certain comedians

that they would rather swim than be passengers on those comedians’ boats. More

formally, for each ordinary person pj (for j ∈ {1, 2, . . . , 2k}), there is some subset Sj

of the total set of comedians {c1, . . . , ck} with which they are willing to ride. Under

the constraint that each of the 2k ordinary people needs to be assigned to a boat

operated by a comedian whose jokes they will tolerate, and given that each boat

can hold two ordinary people, the ship passengers wonder whether it is possible to

evacuate everyone aboard.

Show how efficiently answering this question can be reduced to a Max-Flow problem.

4 Probability (not worth any marks, but still important)

A coin comes up heads with probability 1/3 and tails with probability 2/3.

(a) Suppose that the coin is tossed n times. What is the probability that heads occurs

exactly once?

(b) What is the expected number of coin tosses needed to get the first heads?

学霸联盟

Problem Set 3

Network Flows and Probability

Due: 11:55pm Thursday, March 18, 2021

1 Min-Cut and increasing all edge capacities by 1 (10 marks)

A friend makes the following claim: “Let G be an arbitrary flow network and let

(A∗, B∗) be a minimum s-t cut. Now, let’s increase the capacity of each edge by 1.

Then (A∗, B∗) must still be minimum s-t cut.”

Is the friend right? Explain why or why not.

2 Max-Flow with Node Capacities (10 marks)

In a standard Max-Flow problem, we assume that edges have capacities, and there

is no explicit limit on how much flow is allowed to pass through a node. We now

consider a variant of the standard problem where nodes, not edges, have capacities.

Let G = (V,E) be a directed graph, with source s ∈ V , sink t ∈ V , and nonnegative

node capacities cv for each v ∈ V . Given a flow f in this graph, the flow through

a node v is defined as f in(v). We call a flow feasible if it satisfies the usual flow-

conservation constraints and the node-capacity constraints: f in(v) ≤ cv for all nodes.

Show how the Ford-Fulkerson algorithm can be used to find a maximum s-t flow in

such a node-capacitated network.

3 Tragic Comedy and Network Flows (10 marks)

A ship full of k comedians and 2k ordinary (non-comedian) people is capsizing. The

hope is to evacuate all people onboard via rescue boats. Fortunately, each comedian

has one rescue boat (in case they had to escape a tough crowd), and each boat can

carry two additional passengers (for a total of one comedian and two non-comedians).

Therefore, if the non-comedians could be arbitrarily paired up and each pair could

go on one comedian’s boat, everyone could be evacuated.

However, certain ordinary people so strongly dislike the jokes of certain comedians

that they would rather swim than be passengers on those comedians’ boats. More

formally, for each ordinary person pj (for j ∈ {1, 2, . . . , 2k}), there is some subset Sj

of the total set of comedians {c1, . . . , ck} with which they are willing to ride. Under

the constraint that each of the 2k ordinary people needs to be assigned to a boat

operated by a comedian whose jokes they will tolerate, and given that each boat

can hold two ordinary people, the ship passengers wonder whether it is possible to

evacuate everyone aboard.

Show how efficiently answering this question can be reduced to a Max-Flow problem.

4 Probability (not worth any marks, but still important)

A coin comes up heads with probability 1/3 and tails with probability 2/3.

(a) Suppose that the coin is tossed n times. What is the probability that heads occurs

exactly once?

(b) What is the expected number of coin tosses needed to get the first heads?

学霸联盟