# 算法代写 | COMP3027 Algorithms 3027/3927 Assignment 5

这个作业是设计一个算法解决外卖公司香肠和奶酪之间的数量问题

COMP3027 Algorithms 3027/3927 Assignment 5

To liven up your weekend evenings, you decided to order a sausage-cheese platter1

subscription from

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.

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 |

Pn

i=1 S[i][P[i]] −

Pn

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

decision problem.

(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.

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.

2