COMP3027 Algorithms 3027/3927 Assignment 5
To liven up your weekend evenings, you decided to order a sausage-cheese platter1
the new meal-delivery company Kaiser des Wurst-K¨ases. 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.
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] amounts of sausage and C[i] amounts of cheese; similarly, platter 2 contains S[i]
amounts of sausage and C[i] 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 |
i=1 S[i][P[i]] −
i=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-K¨ase
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-K¨ase
(b) Prove the correctness of your reduction, i.e. the instance of the Partition problem is a YES-instance
if and only if the instance of the Wurst-K¨ase decision problem created by your reduction is a YESinstance.
(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.
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.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx