2023年11月25日

算法代写｜CS 5300 Advanced Algorithm Design and Analysis Final Exam

本次美国作业是一个高级算法设计与分析的算法代写限时测试

1. (16 pts) Question:

Decide True or False for the following questions. In each question, justify your answer.

(a) All NP-complete problems are NP-hard.

(b) All NP-hard problems are NP-complete.

(c) If a problem Z is NP-complete, proving that Z is reducible to Y, in polynomial time, is
sufficient to show that Y is NP-complete.

(d) If a problem Z is NP-hard, proving that Z is reducible to Y, in polynomial time, is sufficient
to show that Y is NP-hard.

2. (16 pts) Question:

TWO2ONE-PARTITION Problem :

Instance: A finite set of positive integers Z= {z1,z2,…,zn}.

Question: Is there a subset Z’ of Z such that
Sum of all numbers in Z’ = 2  Sum of all numbers in Z-Z’
SUM-OF-SUBSETS Problem
Instance: A finite set A = {a1,a2,…,am} and M.

Question: Is there a subset A’ in A s.t.  ai = M?
ai in A’

Given that TWO2ONE-PARTITION Problem is NP-Complete, prove that the SUM-OF
SUBSETS Problem is NP-Complete by reducing TWO2ONE-PARTITION Problem to it.

(a) Give a nondeterministic polynomial time algorithm for the SUM-OF-SUBSETS Problem.
(Use Guess statements in your solution, e.g Guess({0,1}) returns 0 or 1)

(b) Define the transformation from the TWO2ONE-PARTITION Problem to the SUM-OF
SUBSETS Problem and give the if-and-only-if proof.