CS577 Assignment 6 – Network Flow
代写算法作业 1.(10 points) The village of Moonlight is organizing a mountain climbing competition. And has attracted many people to attend. Since it ···
For submission (20 points, 10 points for each question) 代写算法作业
1.(10 points) The village of Moonlight is organizing a mountain climbing competition. And has attracted many people to attend. Since it is a long-distance competition and takes 8-10 hours to finish. The organizer decides to divide the whole competition into segments. At the end of each segment, there are n rest stations for the athletes to take an energy drink so that they can continue the competition.
An athlete who could not get an energy drink at a station will file complain to the organizer. And might cause big loss for the organizer. Due to the difficulty of transporting energy drinks on the mountain (have to be carried by people). The supply of energy drink at each stop is limited at ????,?? with i=1,2,…m denotes the segment number and j=1,2,…n denotes the rest station number at the end of segment i. After one leaves station j=1,2,…n-1 at the end of segment i=1,2,…m-1, there are two paths that takes the same time to lead to station j. And j+1 at the end of segment i+1.
For station n, there are two paths that takes the same time to lead to station n and n-1 at the end of the next segment i+1. Everyone will start from the same starting spot. And there are roads from the starting point to every station at the end of the first segment that takes the same time. In addition, every station at the end of segment m-1 has a path to the ending point that takes the same time. Now you are asked to plan for the event to decide the maximum number of athletes that should be sent to the starting point and avoid any complain.
Note that you should: 代写算法作业
(1) ( 6 points) Present your algorithm idea, construct a network flow model for this problem. And clearly state the meaning of each component (node, edge, capacity) of the flow network that you construct, present your algorithm in pseudocode. And give the computing complexity analysis of your algorithm.
(2) ( 4 points) Present the analysis on the correctness of your algorithm. Specifically, you should:
a.Show that a solution to the original problem will result in flows (i.e. satisfies the conservation and capacity conditions) in the network flow graph G.
b.Show that the solution to the network flow problem will give the solution to the original problem.
2.(10 points) The MayFlower consulting company has a new building and hope to move all of their n employees to the new building. As the new building provide better facility and enable higher working efficiency, moving employee i to the new building will lead to a benefit of ???? ≥ 0. However, two special employees denoted as employee n-1 and employee n become allergic once they enter the new building, and that is why they have to stay in the old building. The employees need to collaborate with each other and if employees i and j have extensive interactions but are working in different buildings, a cost of ?????? will be triggered.
代写算法作业
Now the question is, which of the remaining n-2 employees should be moved to the new building so that the maximum net benefits (i.e. the total benefit minus the cost) can be achieved for the company? Give a polynomial-time algorithm to find the optimal solution. Note that you should:
(1) (6 points) Present your algorithm idea, construct a network flow model for this problem and clearly state the meaning of each component (node, edge, capacity) of the flow network that you construct, present your algorithm in pseudocode, and give the computing complexity analysis of your algorithm.
(2) (4 points) Reason on the correctness of your algorithm. Specifically, you should:
a.Show that a solution to the original problem will result in flows (i.e. satisfies the conservation and capacity conditions) in the flow network graph G.
b.Show that the solution to the network flow problem will give the solution to the original problem.
Not required for submission (for your practice)
- Erickson book Chapter 11, Q.5 (pp. 369-370) .
- Kleinberg book Chapter 7, Q.26 (pp. 430).
更多代写：java代写价格 siele代考 案例分析 美国essay格式 HIS代写 圣彼得堡学院代写
