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:
![](https://dsd5zvtm8ll6.cloudfront.net/si.experts.images/questions/2023/09/65098d7f1a724_1695124856143.jpg)
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...
-
What are typical measures of productivity used by retailers that focus on each of the following: price, assortment, quality, and customer service? What is the image of the retailer?
-
Please just discuss the rules for a ballet dancer and a good college student Discuss the three levels of Measurement (conceptual, operational, rules) for two of the following three items: 1) a good...
-
2 Develop a matrix to compare the five elements of the promotional mix on three criteriato whom you deliver the message, what you say, and when you say it.
-
Multiple Choice Questions The auditor would send a bank confirmation to all banks with which the client had business during the year, because a. The confirmation seeks information on indebtedness...
-
At December 31, Hawke Company reports the following results for its calendar year. Cash sales Credit sales $ 400,000 $ 1,000,000 In addition, its unadjusted trial balance includes the following...
-
write a closed-research legal memo using the case cases given, addressing whether Mr. Adler can assert an adverse possession claim to Scrub Lot 40. Please write up your memo using the issue , brief...
-
Question 25 (0.5 points) An investment project has only the following cash flows: initial cash outflow is $2,000,000; cashflow from year 1 through year 8 is $400,000 each (i.e. cash inflow in year 1...
-
If a change were made to Technical Spec 2 in the product's design, this would likely change the customer's opinion of which value feature the most? Quick Start Quick Start QFD Matrix 1 = Strong...
-
You are a quality management consultant for the Beserk Tennis Ball Company. Beserk is redesigning its current model of tennis ball, and you are asked to use QFD analysis to make suggestions about...
-
You are reviewing a tender evaluation that is to be awarded on lowest total price. The bid evaluations follow: To which company should the contract be awarded? Company Capital Cost Maintenance...
-
You have invited four companies to bid on a consulting project. All four companies answered your invitation to tender, but the bids vary in the number of hours each company estimates will be required...
-
Boston Cycles inventory data for the year ended December 31, 2011, follow: Assume that the ending inventory was accidentally overstated by $2,200. Requirement 1. What are the correct amounts for cost...
-
5. Dragonstone Corp. had net income of $32,000. Accounts Receivable increased by $3,000; accounts payable decreased by $4,000. Depreciation expense for the year was $1,400. Additional transactions...
-
Government is advised to tax goods whose demand curves are inelastic if the goal is to raise tax revenues. If the goal is to discourage consumption, then it ought to tax goods whose demand curves are...
-
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?
-
36. The City of Francois, Texas, has begun the process of producing a comprehensive annual financial report (CAFR). Several organizations that operate within the city are related in some way to the...
-
38. The following information pertains to the City of Williamson for 2008, its first year of legal existence. For convenience, assume that all transactions are for the General Fund, which has three...
-
39. The City of Bernard starts the year of 2008 with the following unrestricted amounts in its Gen eral Fund: cash of $20,000 and investments of $70,000. In addition, it holds a building bought on...
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App