# CS计算机代考程序代写 AI algorithm CSCI-570 Homework 4

CSCI-570 Homework 4
April 6, 2020
1 Compute Max-Flow And Min-Cut
Solution: Figure 1 has max-flow 7. One feasible flow is S → A → C → T withflow2,S→A→B→C→T withflow1,S→B→D→T withflow 3 and S → B → C → T with flow 1. All min-cuts are {S}||{A,B,C,D,T}, {S,A,B,D}||{C,T}. Figure 2 has max-flow 7. A feasible flow is S → A → T withflow3,S→B→T withflow3andS→B→A→T withflow1. All min-cuts are {S, B}||{A, T }, {S}||{A, B, T }.
A2C A
3635 4
S1 TS11T 12
4343 B3D B
Rubric: Each subproblem has 5 points. 2 points for correct max-flow value, 1 point for any feasible max flow and 2 points for the two min cuts.
2 Escape From the Building
In this problem, we need to decide whether there is a feasible plan for all the persons in a building to escape when they meet some emergency issues. More specifically, a building is described as an n by n grid and the position of p persons are represented as the integer points (x1, y1), . . . , (xp, yp) in the building. Note that to ensure safety, we don’t allow any intersection between the paths of any two person. Therefore, your task is to decide whether there exist p vertex-disjoint paths from their starting points to any p different points on
1

the boundary of the grid. Give an algorithm polynomial in n and prove the
correctness of it.
Solution: We construct the network as follows. First, we split each point
(i, j) in the grid into two points (iin, jin) and (iout, jout) and add an edge with
capacity 1 from (iin, jin) to (iout, jout). In addition, for all (iout, jout), we add
directed edges to its adjacent in-node, namely (i + 1in, jin), (iin, j + 1in), (i −
1in, jin) and (iin, j − 1in) if they are well defined already. Then, We add a
source node S and add an directed edge from S to each start in-node (xin,yin) ii
with capacity 1, i ∈ [p] and finally, we add a sink node T and connect all the boundary out-node (iout,jout) to it with a directed edge of capacity 1. Our algorithm is to first compute an integer max-flow of this graph by using Edmund- Karp algorithm. According to our construction, the value of the max-flow is no more than p.
Claim: There exist p disjoint paths if and only if the above network has a max-flow of value p.
Proof: If there exists a max-flow of value p, we can construct p disjoint
paths according this flow. Specifically, for each (xi,yi), there must be one unit
flow from S to (xin, yin) the finally it will reach the sink, which means it reaches ii
one of the boundary point. This one unit flow therefore indicates a path from (xi,yi) to one of the boundary point. Also, these paths will never intersect. If so, there would be two units coming into one in-node. As the corresponding out-node is of capacity 1, it is not feasible.
On the other hand, if the value of the max-flow is not p, we claim that there
does not exist such p disjoint paths because if there exists p disjoint paths, we
can construct a flow of value p by following these paths. Concretely, for a path
(xi,yi) → (xi + 1,yi) → ··· → (x∗,y∗) (The last one is the boundary point),
we have a one unit flow S → (xin,xout) → (xout,yout) → (x + 1in,yin) → iiiiii
(xout,yout) → ··· → (x∗in,y∗out). for each i ∈ [p]. This is a feasible flow as ii
the p paths are disjoint. Therefore, we show the correctness of our algorithm and the runtime is polynomial in n as the complexity of generating graph and translating the solution and Edmond Karp algorithm are all polynomial in n.
Rubric: 5 points for giving correct directed graph with capacity. 4 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) (Running FF here is correct as it is polynomial time in this case.)
3 Install Software to Your New Computer
Suppose that you have just bought a new computer and you want to install soft- ware on that. Specifically, two companies, which you can think of like Microsoft and Apple, are trying to sell their own copy of n different products, like Opera- tion System. Spread Sheet, Web Browser. For each product i, i ∈ {1, 2, . . . , n}, we have
• the price pi ≥ 0 that Microsoft charges and the price p′i ≥ 0 that Apple charges.
2

• the quality qi ≥ 0 of Microsoft version and the quality qi′ ≥ 0 of Apple version.
For example, Apple may provide a better Web Browser Safari, but Microsoft a better Word Processor. You want to assemble your favorite computer by installing exactly one copy of each of the n products, e.g. you want to buy one operating system, one Web Browser, one Word Processor, etc. However, you don’t want to spend too much money on that. Therefore, your goal is to maximize the quality minus total price.
However, as you may know, the products of different companies may not be compatible. More concretely, for each product pair (i, j), we will suffer a penalty τij ≥ 0 if we install product i of Microsoft and product j of Apple. Note that τij may not be equal to τji just because Apple’s Safari does not work well on Microsoft Windows doesn’t mean that Microsoft’s Edge does not work well in Mac-OS. We assume that products are always compatible internally, which means that there is no penalty for installing two products from the same company. All pairwise penalties will be subtracted from the total quality of the system.
Your task is then to give a polynomial-time algorithm for computing which product i to purchase from which of the two companies (Apple and Microsoft) for all i ∈ {1,2,…,n}, to maximize the total system quality (including the penalties) minus the total price. Prove the correctness of your algorithm. (Hint: You may model this problem as a min-cut problem by constructing your graph appropriately.)
Solution: In this problem, we actually need to separate the objects into two parts A (Microsoft) and B (Apple) so that we can maximize the following:
max􏰁qi+􏰁qj′− 􏰁 τij−􏰁pi−􏰁p′j. i∈A j∈B i∈A,j∈B i∈A j∈B
With a little calculation, we can transform the above objective function as follows:
􏰁qi+􏰁qj′− 􏰁 τij−􏰁pi−􏰁p′j i∈A j∈B i∈A,j∈B i∈A j∈B
 
=􏰁(qi+qi′)− 􏰁qj+􏰁qi′+ 􏰁 τij+􏰁pi+􏰁p′j . i∈[n] j∈B i∈A i∈A,j∈B i∈A j∈B
Note that 􏰀i∈[n](qi +qi′) is a constant in this problem. Therefore, to maximize the original objective, we are to minimize the following:
 
min 􏰁qj +􏰁qi′ + 􏰁 τij +􏰁pi +􏰁p′j . j∈B i∈A i∈A,j∈B i∈A j∈B
3

Then we can model this problem as a min-cut problem by constructing the graph as follows. First, we add a source node s and a sink node t. For each object j, we add one node Aj . We add an edge from S to Aj with capacity p′i +qi and add an edge from each Aj to T with capacity pj + qj′ . For the correlation between objects, we add an edge from Ai to Aj with capacity τij.
Claim: The above minimization problem has an optimal value v if and only if the above constructed network has a max-flow (min-cut) of value v.
Proof: If there is a cut of value v in the network, then actually this cut contains two parts of nodes. One part contains S and the other part contains T. Then, we just assign the objects corresponding to the nodes belonging to S to A and assign the objects corresponding to the nodes belonging to T to B. Forthecutvalue,ifnodeiisinAandnodejisinB,wewillcutthe edges from S to Aj, Ai to T and Ai to Aj. These edges are of total capacity p′j + qj + pi + qi′ + τij , which is exactly the corresponding term in the above objective function. Therefore, we can achieve v by assigning n objects to either A or B.
On the other hand, if the optimal value of the minimization problem is v, then there must be an assignment of the n objects. Then we just cut the network into two parts. One part includes S and objects in A and the other part includes T and objects in B. It is similar to the former direction to show that the cut value here equals v. Based on the above observations, we prove the claim.
Therefore, our algorithm is to first construct the above network, use Edmund- Karp (as here we require polynomial algorithm) to obtain a max-flow of that graph, traverse along the max-flow to obtain a corresponding min-cut and assign the objects belonging to S to Microsoft and the others to Apple. The construc- tion of graph, Edmond-Karp algorithm, traversing and assigning can all be done in polynomial time. The correctness is proved by the above analysis.
Rubric: 3 points for giving correct transformation of the original prob- lem. 3 points for giving the correct directed graph with capacity. 3 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) (Note: if the students mention Ford-Fulkerson Algorithm with pseudo-polynomial time, give a 2 points deduction.)
4 Jumping Frogs
Somewhere near the Algorithmville, a number of frogs are standing on a num- ber of lotus leaves. As they are social animals (and yes, they are never infected by coronavirus!), the frogs would like to gather together, all on the same lotus leaf. The frogs do not want to get wet, so they have to use their limited jump distance d to get together by jumping from piece to piece. However, these lotus leaves just started to grow, they will get damaged further by the force needed to jump to another leaf. Fortunately, the frogs are real experts on leaves, and know exactly how many times a frog can jump off each leaf before it sinks and become unavailable. Landing on leaves does not damage it. You have to help the frogs find a leaf where they can meet.
4

In this question, we will get the position of N lotus leaves. For each i ∈ [N], we know its position (xi, yi), the number of frogs ni on that leaf and the number of jumps mi before it sinks. The distance between two leaves (xi, yi) and (xj , yj ) is defined as |xi − xj | + |yi − yj |. Design an polynomial algorithm to determine whether each lotus leaf can hold all frogs for a party. The output is an array with length N, containing yes/no solution.
Solution: The trick in this question is the limit of ”departure” on each leaf. To model that, we split each node to be ”departures” and ”arrivals”. The exact graph is described as follows:
• We have a source node s.
• We build N arrival nodes ai. s is linked to every ai with capacity ni.
• We build N departure nodes di. Each ai is linked to di with capacity mi.
• For a pair of leaves (i,j), we link di to aj and dj to ai, with capacity ∞, if |xi − xj| + |yi − yj| ≤ d, i ̸= j.
Then we run the Edmond-Karp (polynomial time algorithm) algorithm with source node s to sink node ai to determine that whether the max-flow value equals to 􏰀Ni=1 ni. If so, we know that the leaf i is a valid spot. We repeat the max-flow algorithm for all i ∈ [N], then we can output the yes/no solution for each leaf.
Claim: The max flow value of the graph with source s and sink ai is 􏰀Ni=1 ni if and only if there exist a way that all frogs gather together.
Proof: (flow value → gathering plan) To give a feasible plan from a feasible flow with value 􏰀Ni=1 ni, we consider each unit flow as a frog. Surely for each leaf i, there are ni frog on it, which in the graph means that ni units flow are sent to it in the feasible flow of value 􏰀Ni=1 ni. Then consider leaf i as sink and other leaf j, j ̸= i, how do we let the nj frogs arrive at leaf i? For each
5

j ̸= i, we follow the flow from aj to ai, which we assume as the following kj paths: aj → dj → ajl,1 → djl,1 → · · · → ajl,k1 →djl,k1 →ai with fl,j units flow for
l ∈ [kj]. Then we just let fl,j frogs jump from leaf j to jl,1, to jl,2 till i for all j ̸= i. This is a feasible plan as according to the construction of the graph, no more than mj units of flow can leave from aj, which means no more than mj frogs can leave from leaf j. It also makes sure that the frogs gather together at leaf i as the value of the flow is the total number of frogs. So every frog ”flows” to leaf i.
(gathering plan → flow value) For each gathering plan, we can interpret it in the similar way above. Consider a plan that all frogs gather to leaf i. Frogs on leaf j have the following kj different paths: aj → dj → ajl,1 → djl,1 → · · · → ajl,k1 →djl,k1 →ai with fl,j frogs flow for l ∈ [kj ], then we just send the corresponding value of flow along the path. This will not violate the constraints of the graph as leaf j can only handle mj leaves. In addition, the flow value is 􏰀Ni=1 ni as the plan is feasible, which means that for each node i, we are sending ni units of flow.
Rubric: 5 points for giving correct directed graph with capacity. 4 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) (Note: if the students mention Ford-Fulkerson Algorithm with pseudo-polynomial time, give a 2 points deduction.)
5 Preparing for the Exams
My friend Leo wants to have a emergency plan for his final exams on University of Southern Algorithmville. He has N subjects to prepare for, and for each subject, his score is determined only by the time he spend on learning. It’s not surprising that Leo found out he actually spent zero time on preparing before.
At least he knows when he can start learning all of these subjects. For each subject i there is a start time si when he can get all materials ready to
6

start learning. And there is also a ending time ei for each subject, when his learning materials expire and he can’t learn anymore. We know that si and ei are integers, and Leo can only dedicate to a single subject within each time phase.
In the University of Southern Algorithmville (USA), a student’s total grade is the minimum grade among all subjects. Leo wants you to help him find out the best outcome. Given N subjects and their time intervals (si,ei), design an algorithm to find out the maximum time possible for the least prepared subject. (Hint: It’s not enough to use the network flow algorithm alone to determine the answer.)
Solution: Consider that we want to learn for k-unit time for each subject. The problem now become determining the feasibility of learning for k time. We can build the following graph Gk:
• s is the source node.
• (The layer of subject) pi,i ∈ [N] are the nodes for each subject. We link
s → pi for every pi with a link with capacity k.