There are a group of n new employees in Bright Coding company like to hang out...
Fantastic news! We've located 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.
Expert Answer:
Answer rating: 100% (QA)
The answer of this question money paid by employee1 2 n were P1 P2 PN There are a group of n new emp 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

The Crazy Eddie fraud may appear smaller and gentler than the massive billiondollar 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...

The yields of nine batches of a chemical process were measured and a sample mean of 2.843 and a sample standard deviation of 0.150 were obtained. The experimenter presented a confidence interval of...

Determine the assets to revenues ratio for the construction company in Figures 63 and 64. What insight does this give you into the companys financial operations? FIGURE 63 Balance Sheet for...

Consider the situation shown in Fig. P8.45. Ball A of mass 2m is raised to a height of h so that its string makes an angle of 45 with the vertical, and it is then let go. To what height will ball B...

How does the contractor know exactly when he can expect payment?

On July 2, 2009, the McGraw Corporation issued $500,000 of convertible bonds. Each $1,000 bond could be converted into 20 shares of the companys $5 par value stock. On July 3, 2011, when the bonds...

Suppose that a familys income grew from $38,000 to $38,100 over the period 2009 to 2010, which saw an inflation rate of 2 percent. We can conclude that this family experienced: An increase in both...

Using the results of Problem 1.7, show that de r / d = e and de /d = e r . Data From Problem 1.7 Show that the unit vectors e r and e in a cylindrical coordinate system are related to the unit...

Etobicoke Enterprises is deciding whether to expand its production facilities. Although longterm cash flows are difficult to estimate, management has projected the following cash flows for the first...

Consider the country of Cambria and its balance of payments. We should expect in this country that: Positive entry is recorded for changes in foreign currency reserves in Cambria's balance of...

A company just purchased a $10 million building that depreciates evenly over 10 years (straightline depreciation). The tax rate is 30%. What is the effect on the balance sheet?

Taxpayer is a successful painter. A local art gallery contacted him about staging an art show. As part of the offer, the gallery would also purchase five of his oil paintings for a total payment of...

Where a company has an 25% investment in an associate how are the company 's share of the associate's losses accounted for ? If the associate continues to make losses what happens to the investment...

" Status Play", Privilege walk Activity" and "Acculturation strategies" .Explain.

Lets assume that both employees have reached the maximum pay rates for their jobs, as reflected in the pay they received in 2016. Under a longevity pay system, calculate the annual longevity payments...

The executor of Gina Purcells estate has recorded the following information: Assets discovered at death (at fair value): Cash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....

Why is it important that final activities not be openended?

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?

Consider a hypothetical economy in which each worker has to decide whether to acquire education and become a highskilled worker or remain lowskilled. Education carries a cost of C. Assume that...

You are the minister of planning in a developing country with a poorly developed industrial sector. You would like to create a climate in which industrialists will invest and create economic growth....

Complementarities arise in all sorts of situations. Here is a tax evasion problem. Suppose that each of N citizens in a country needs to pay a tax of T every year to the government. Each citizen may...
Question Categories