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.