首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28
- 代做csci 151程序实验、代写programming编程、C+,Java 2021-02-28
- 代写data编程、R留学生程序代做、代写r编程语言代做留学生processi 2021-02-28
- 代写csce 440编程、代做java，Python程序语言帮做c/C++编 2021-02-28
- Cst2330程序代做、Data Analysis程序代写、代写python 2021-02-28
- 代写cmpsc473编程、C++程序设计调试、代写data编程课程调试mat 2021-02-28
- Comp3018 Coursework 2 2021-02-27
- Write A Report To Describe The Analysi... 2021-02-27
- Mlp 2020/21: Coursework 2 2021-02-27
- Stat-3503 Statistics Minors And Study ... 2021-02-27
- Beng0091编程代写、代做r编程实验、R程序设计调试代写r语言程序|代写 2021-02-27
- Ee2028a程序代写、Programming程序语言代做、代写c/C++课 2021-02-27
- Program程序设计代做、C++课程编程代写、C++语言程序调试帮做c/C 2021-02-27
- 代写data留学生编程、代做c/C++程序语言代做r语言程序|代做数据库sq 2021-02-26
- Pic 10B留学生程序代做、C/C++程序调试、C++编程实验代写代写r语 2021-02-26
- 代写csci 4116程序、代做python，Java程序实验、C++编程代 2021-02-26