There are a group of n new employees in Bright Coding company like to hang out...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
There are a group of n new employees in Bright Coding company like to hang out together before pandemic. For every activity (dining, watching a football game, boating etc.) they attended, the bill was always paid by a single person although everyone agreed to pay the fair share in the end. When the pandemic came and no more activities were planned, the group decided it is the time to settle up the bills. After retrieving the accounting details, they found that the money paid by employee 1,2,....n were P, P2,..., Pn. For those people who have paid less than the fair share, they need to write checks to pay those who have overpaid than their share. After the checks were written and cashed, no one should own money to any other. However, there are two people who are supposed to write checks did not like to write more than one check, and one people who should get paid does not want more than one check. Your job is to design a network flow algorithm to find out whether the requirement of these three people can be satisfied while all payments will be settled, and if yes, find out the details of each check: the amount, and who paid who. Note that you should: (1) (5 points) Construct a network flow model for this problem. Clearly state the meaning of each component (node, edge, capacity) of the flow network that you construct, draw out a flow network graph, describe your algorithm idea (you don't have to write the pseudocode), and give the computing complexity analysis of your algorithm. (2) (5 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 you set up will give the solution for the original problem. There are a group of n new employees in Bright Coding company like to hang out together before pandemic. For every activity (dining, watching a football game, boating etc.) they attended, the bill was always paid by a single person although everyone agreed to pay the fair share in the end. When the pandemic came and no more activities were planned, the group decided it is the time to settle up the bills. After retrieving the accounting details, they found that the money paid by employee 1,2,....n were P, P2,..., Pn. For those people who have paid less than the fair share, they need to write checks to pay those who have overpaid than their share. After the checks were written and cashed, no one should own money to any other. However, there are two people who are supposed to write checks did not like to write more than one check, and one people who should get paid does not want more than one check. Your job is to design a network flow algorithm to find out whether the requirement of these three people can be satisfied while all payments will be settled, and if yes, find out the details of each check: the amount, and who paid who. Note that you should: (1) (5 points) Construct a network flow model for this problem. Clearly state the meaning of each component (node, edge, capacity) of the flow network that you construct, draw out a flow network graph, describe your algorithm idea (you don't have to write the pseudocode), and give the computing complexity analysis of your algorithm. (2) (5 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 you set up will give the solution for the original problem.
Expert Answer:
Answer rating: 100% (QA)
The answer of this question money paid by employee12n were P1 P2PN There are a group of n new employ... View the full answer
Related Book For
Project Management The Managerial Process
ISBN: 9781260570434
8th Edition
Authors: Eric W Larson, Clifford F. Gray
Posted Date:
Students also viewed these algorithms questions
-
A planetary gear train shows the numbers of teeth of T = 32,T= 14 60. Determine the velocity ratio when (1) Sun gear 2 serves as the input, Carrier 5 serves as the output, and Ring gear 4 is braked....
-
The Crazy Eddie fraud may appear smaller and gentler than the massive billion-dollar frauds exposed in recent times, such as Bernie Madoffs Ponzi scheme, frauds in the subprime mortgage market, the...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
At the beginning of the year, Plummer's Sports Center bought three used fitness machines from Advantage, Inc. The machines immediately were overhauled, installed, and started operating. The machines...
-
Unitroj Inc., reported pretax financial accounting income in 2011, 2012, 2013 and 2014 of $100 million. In 2011, Unitroj purchased a machine for $100 million with a useful life of five years. The...
-
Revco Electronics is a division of International Motors, an automobile manufacturer. Revco produces car radio/CD players. Revco sells its products to International Motors, as well as to other car...
-
2. Suppose that you are the manager of the General Motors Hummer plant in Mishawaka, Indiana. Hummers are the successor to the U.S. Army jeep and have become popular recreational vehicles among the...
-
Gibbs Company purchases sails and produces sailboats. It currently produces 1,200 sailboats per year, operating at normal capacity, which is about 80% of full capacity. Gibbs purchases sails at $250...
-
Larry Orangeburg, CEO of Apples and Oranges, Inc., wants to raise $5 million in a private equity in his early stage venture. Orangeburg conservatively projects net income of $ 10 million in year...
-
The trial balance of Jeremina plc as at 31 March 20X2 is as follows: Notes: (i) Stock of finished goods on 31 March 20X2 163,000. (ii) Motor expenses and depreciation on motors to be apportioned:...
-
Look at the P-value to determine if the desired alpha level is met: findings for an ANOVA that analyzes MAAP ELA scores across students in the third through sixth grades. For 3rd grade, the count is...
-
Jose Ruiz manages a construction rm's equipment repair... Jose Ruiz manages a construction firm's equipment repair department. His department is a cost center. Costs for a recent period follow. Jose...
-
The most recent financial statements for GPS, Inc., are shown here: Income Statement Balance Sheet Sales $19,500 Assets $98,000 Debt $52,500 Costs 15,000 Equity 45,500 Taxable income $4,500 Total...
-
Two charged, square plates, separated by a distance of 12.6 cm and each with a side length of 27.1 cm, make up a parallel-plate capacitor. The electric field inside the plates is 1.70x10 3 N/C. If...
-
What volume of a 12.0 M H2SO4 solution would be required to produce 300. mL of 4.0 M H2SO4?
-
1. What are the roles of toroidal and polodial magnetic field on tokamak? 2.Describe the inertial confinement method for nuclear fusion? 3.Why is fusion considered to be safer than fission? 4.How do...
-
Good morning class, What is financial risk management, and why is it important for businesses and organizations? Financial risk management are strategies and processes that businesses used to assess,...
-
Orange juice producers are dismayed and puzzled. An economist told them that the reason the demand for orange juice fell is that a new technology allow tomato producers to pick ripe tomatoes more...
-
Why is it important that final activities not be open-ended?
-
Do you agree with Ron Parkers statement To be successful, you must also be willing to run at problems/opportunities when everyone else is running away from them?
-
What kinds of projects is Agile PM best suited for and why?
-
RJR Nabisco also had $10 billion in bonds outstanding at the time of the dividend increase in Problem 10. How would you expect the bonds to react to the announcement? Why? Reference from in problem...
-
To examine how much cash your firm has returned to its stockholders and in what form (dividends or stock buybacks) and to evaluate whether the trade-off favors returning more or less. Key Questions ...
-
To estimate earnings and cash flows on a typical project for the firm. Key Questions: 1. Does your firm have a typical investment? 2. If so, can you estimate the earnings and cash flows on a typical...
Study smarter with the SolutionInn App