代写data程序、代写Python，Java编程

日期：2022-04-16 11:13

Algorithms 3027/3927 Assignment 3 The University of Sydney

2022 Semester 1 School of Computer Science

3027 students: Do Tasks 1 and 2. 3927 students: Do Tasks 2 and 3.

A little-known fact about the burning of King’s Landing is that all of the coins were also burnt,

leaving behind only gold bars. This presents a dilemma to the Lannisters since a Lannister always pays

his debts but the amount they owe to any individual non-Lannister is often less than a gold bar. They

approach you, the Master of Coin, to help them determine how they can pay their debts in gold bars

such that the total amount paid by each Lannister is exactly his total debt to all non-Lannisters, and

each non-Lannister receives exactly the amount that is owed to them by all Lannisters.

In particular, you are given an k × k table of debts D, where D(i, j) is the amount owed by Lannister

i to non-Lannister j. Each amount D(i, j) is a fraction satisfying 0 ≤ D(i, j) ≤ 1 representing a fraction

of a gold bar. A debt table D is said to be proper if it satisfies the following properties:

1. P

j D(i, j) is an integer for every i, i.e. total debt of each Lannister is an integer.

2. P

i D(i, j) is an integer for every j, i.e. total debt owed to each non-Lannister is an integer.

We say that an k × k table of payments P, where P(i, j) represents the number of gold bars to be

paid by Lannister i to non-Lannister j, is feasible if it satisfies the following constraints:

1. (Integrality) P(i, j) must be either the ceiling or floor of D(i, j).

2. P

j P(i, j) = P

j D(i, j) for every i, i.e. each Lannister pays exactly his total debt to all nonLannisters.

3. P

i P(i, j) = P

i D(i, j) for every j, i.e. each non-Lannister receives exactly the total debt owed to

them by all Lannisters.

We say that a debt table D is admissible if it has a proper feasible payment table.

Your goal is to determine, given a debt table D, whether it is admissible and if so, to output a feasible

payment table. We call this the Feasible Payment Problem.

For example, suppose D is the following proper debt table:

Brandon Sansa Arya

Cersei 0.9 0.6 0.5

Jaime 0.9 0 0.1

Tyrion 0.2 0.4 0.4

Figure 1: The debt table D

It is admissible because the following table P is feasible:

Brandon Sansa Arya

Cersei 1 1 0

Jaime 1 0 0

Tyrion 0 0 1

Figure 2: A feasible payment table P

Task 1 (3027 only): Greed does not pay [20 marks]

Once again, you start by brainstorming out loud with Rubber Duck. This time, Rubber Duck goes first.

Rubber Duck: “Hmm... Do we really need to use this flow thingamajig? What about the following

greedy algorithm? We start with P having all zeros. Then, we iterate through each entry of P. For the

current entry P(i, j): if D(i, j) = 1 or D(i, j) = 0 then we can only set P(i, j) = D(i, j); otherwise, if

1

Lannister i has not already paid his debt (i.e. P

j

0 P(i, j0

) <

P

j

0 D(i, j0

)) and non-Lannister j has not

already received the debt owed to them (i.e. P

i

0 P(i

0

, j) <

P

i

0 D(i

0

, j), then we set P(i, j) = 1, else we

set P(i, j) = 0. If P is feasible, then we output P. Otherwise, D is not admissible.”

Algorithm 1 Greedy algorithm

1: procedure Greedy(D)

2: Initialize P such that P(i, j) ← 0 for every 0 ≤ i ≤ k − 1 and 0 ≤ j ≤ k − 1.

3: for i = 0 to k − 1 do

4: for j = 0 to k − 1 do

5: if D(i, j) = 0 or D(i, j) = 1 then

6: P(i, j) ← D(i, j)

7: else

8: if P

j

0 P(i, j0

) <

P

j

0 D(i, j0

) and P

i

0 P(i

0

, j) <

P

i

0 D(i

0

, j) then

9: P(i, j) ← 1

10: else

11: P(i, j) ← 0

12: end if

13: end if

14: end for

15: end for

16: if P is feasible then

17: Return P

18: else

19: Return “Not admissible”

20: end if

21: end procedure

You: “Hmm... It does seem reasonable. But as a quick sanity check, does it even work on the example

D above?”

Rubber Duck: “Yes, I’ve run it on that example, and it actually produces the same P as the one

above”

Your task is to come up with a debt table D that admits a feasible payment table but when it is

given as input to the greedy algorithm, the output P of the greedy algorithm is not feasible payment

table. In particular, P does not satisfy at least one of the 3 constraints of a feasible payment table. This

is not an easy counter-example question. Highlight the following and copy for hint [Hint: Use a 3 × 3

table D that is proper and has each entry D(i, j) either 0, 1/2 or 1.]

Note: the solution to this task is to be submitted on Ed so that it can be auto-marked. Details TBA

next week.

Task 2: Feasible Payment Problem [80 marks]

Your task is to design an efficient reduction from the Feasible Payment Problem to an instance of max

flow. It is easy to see that D is not admissible if it is not proper. Thus, for this task, we will assume that

D is proper.

(a) Describe how you translate an instance of the Feasible Payment Problem into an instance of Max

Flow. In particular, you need to describe how, given a proper debt table D, to construct the flow

network H of your Max Flow instance.

(b) State which algorithm you use to compute the max flow in H.

(c) Describe how you translate the output of the algorithm in b) into a solution for the Feasible Payment

Problem. In particular, describe how you determine if D is admissible and if so how you construct

the payment table P.

2

(d) Prove the correctness of your reduction. In particular, you need to prove that there exists an integer

T for which the following two statements hold:

(i) If the max flow in H is at least T, then your translation procedure in (c) produces a feasible

payment table P.

(ii) If there is a feasible payment table P, then the max flow in H is at least T.

(e) Prove the time complexity of your entire algorithm, taking into account the steps in parts (a), (b)

and (c). Make sure that your time complexity is stated in terms of k.

Task 3 (3927 only): [20 marks]

Your task is to prove that if a debt table D is proper, then it always has a feasible payment table P.

In other words, a debt table D is admissible if and only if D is proper. Highlight the following and copy

for hint [Hint: Use the flow network from Task 2 and the Max-Flow Min-Cut Theorem]

Submission details

• Submission deadline is Wednesday 20 April, at 23:59. No late penalties for this assignment.

Submissions later than Friday 22 April, 23:59 will not be accepted.

• Familiarize yourself with following Ed posts and resources:

– General Assignment Guidelines https://edstem.org/au/courses/7844/discussion/752742

– How to Approach Problems https://edstem.org/au/courses/7844/resources?download=

13488

• Submit your answers as a single document to Gradescope. Your work must be typed (no images of

text, although you can use diagrams if you think it helps.) Please try to be reasonably concise.

• The solution for Task 1 is to be submitted on Ed to be auto-marked (more detailed instructions

will be announced later).

• Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s

acceptable to discuss high level ideas with your peers, but you should not share the detail of your

work, such as parts as the precise algorithms, examples, proofs, writing, or code.

• To facilitate anonymous grading, please do not write your name on your submission.

3