Algorithms 3027/3927 Assignment 5 The University of Sydney
2020 Semester 1 School of Computer Science
This assignment is for COMP3027 students only.
To liven up your weekend evenings, you decided to order a sausage-cheese platter1 subscription from
the new meal-delivery company Kaiser des Wurst-Ka¨ses. The subscription is for n weeks, and you need
to choose from one of two platters each week. The two platters have different amounts of sausage and
cheese and also vary in different weeks. As it is important to eat a balanced diet, your goal is to choose
a platter for each week so that the absolute difference between the total amount of sausage and the total
amount of cheese is small enough.
Formal specification
You are given as input two n × 2 arrays S and C, and a non-negative integer b. In week i, platter 1
contains S[i][1] amounts of sausage and C[i][1] amounts of cheese; similarly, platter 2 contains S[i][2]
amounts of sausage and C[i][2] amounts of cheese. A subscription is an n-element array P where P [i]
denotes the platter choice in week i, i.e. P [i] = 1 if platter 1 is chosen and P [i] = 2 if platter 2 is chosen.
The imbalance of a subscription P is |∑ni=1 S[i][P [i]]−∑ni=1 C[i][P [i]]|, the absolute difference between
the total amount of sausage and the total amount of cheese included in the subscription. The Wurst-Ka¨se
decision problem is to decide if there exists a subscription with imbalance at most b.
Task 1: Prove decision problem is in NP [20 marks]
(a) Describe a certificate and a verifier.
(b) Give a brief justification of the correctness of the verifier.
(c) Give a brief justification that the verifier runs in polynomial time.
Task 2: Prove decision problem is NP-hard [40 marks]
Your task is to give a polynomial-time Karp reduction from the Partition2 problem.
(a) Describe how you transform an instance of the Partition problem into an instance of the Wurst-Ka¨se
decision problem.
(b) Prove the correctness of your reduction, i.e. there exists a subscription with imbalance at most b if
and only if the instance of the Partition problem created by your reduction is a YES-instance.
(c) Prove that your reduction is polynomial-time.
Task 3: Reduce search to decision [40 marks]
Suppose that you are given a black box that can solve any instance of the decision problem. In particular,
the black box takes as input S,C, b, and correctly outputs whether there exists a subscription with
imbalance at most b. Your task is to design an algorithm that outputs a subscription P with imbalance
at most b if one exists or outputs NO if none exists, using the black box as a subroutine.
1. Describe your algorithm.
2. Prove the correctness of your algorithm.
3. Prove the time complexity of your algorithm in terms of n, the size of the original input and the
number of calls to the black box.
1Vegan options also available.
2See Tutorial 9.
1
Level of detail required in this assignment
• Please do not write pseudocode (it’s an unnecessarily precise level of detail for these reductions,
and usually harder to follow than prose.)
• Please try to be fairly concise.
• It’s reasonable to write things like these without having to explain precisely how it’s done:
– ‘check that P is a simple path’
– ‘check that all the subsets are disjoint’
• You don’t need to detail data structures etc., unless the choice of structure is important for showing
that the time complexity is still polynomial.
• Don’t forget that you’re not trying to solve these problems, you only need to find polynomial time
certifiers / polynomial time reductions as appropriate.
Submission details
• Submission deadline is Saturday 16 May, at 23:59. Late submissions will not be accepted.
• Please do not submit in German.
• 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.
• 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.