算法代写|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.


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论