Answered You can hire a professional tutor to get the answer.
The m-f `o fraternity at Rutgers has n student members. In Fall'18, m courses are being offered and for each course i, some subset Si of the...
The mαχ-f `oω fraternity at Rutgers has n student members. In Fall'18, m courses are being offered and for each course i, some subset Si of the fraternity members are taking the course together. They have come up with the following cheating scheme: For each course i, some member in the set Si will be responsible for doing all the work in that course, and other members of Si will simply copy the work. Since people would rather not work, they want the responsibility be divided as fairly as possible. Your task in this problem is to give an algorithm to do it efficiently. The fairness criterion is the following: Say that person p is in some k of the sets, which have sizes n1, n2, . . . , nk, respectively. Person p should really have to be responsible for 1 n1 + 1 n2 + · · · + 1 nk courses, because this is the amount of resource that this person effectively uses. Of course this number may not be an integer, so let's round it up to an integer. The fairness criterion is simply that she should not be responsible for more than these many courses. For example, say that there are two courses, and Alice and Bob are taking course 1 together, and Alice, Carl, and Dilbert are taking course 2 together. Alice's fair cost would be d 1 2 + 1 3 e = 1. So Alice being responsible for both the courses would not be fair. Any solution except that one is fair.
• Prove that there always exists a fair solution.
• Give a polynomial-time algorithm for computing a fair solution from the sets Si .
[Hint: Try to model the problem using network flow in such a way that part 1 falls out directly from the integrality theorem for network flow, and part 2 just follows from the fact that we can solve max flow in polynomial time. So, it all boils down to coming up with the right flow graph to model the problem.]
