Java代写|CS 5300 01 Advanced Algorithm Design and Analysis Homework

本次美国代写是一个Java高级算法设计喝分析的Homework

1. Let X(1..n) and Y(1..n) contain two lists of n integers, each sorted in nondecreasing
order. Give the best (worst-case complexity) algorithm that you can think for finding

(a) the largest integer of all 2n combined elements.

(b) the second largest integer of all 2n combined elements.

(c) the median (or the nth smallest integer) of all 2n combined elements.
For instance, X = (4, 7, 8, 9, 12) and Y = (1, 2, 5, 9, 10), then median = 7, the nth
smallest, in the combined list (1, 2, 4, 5, 7, 8, 9, 9, 10, 12). [Hint: use the concept
similar to binary search]

2.
1-to-2 PARTITION:

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 x Sum of all numbers in Z-Z’

(a) Obtain the dynamic programming functional equation to solve the 1-to-2 PARTITION
problem.

(b) Give an algorithm to implement your functional equation.

(c) Give an example of 5 numbers with a total of 21 as an input instance for 1-to-2
PARTITION problem, and show how your algorithm works on this input instance.

(d) What is the complexity of your algorithm?

3. Decide True or False for each of the followings. You MUST briefly justify your
answer.

Satisfiability:

Instance: Set U of variables, collection C of clauses over U.

Question: Is there a satisfying truth assignment for C?

(a) If P  NP, then no problem in NP can be solved in polynomial time deterministically.

(b) If a decision problem A is NP-complete, proving that A is reducible to B, in
polynomial time, is sufficient to show that B is NP-complete.

(c) It is known that SAT (Satisfiability) is NP-complete, and 3SAT (all clauses have size
3) is NP-complete. 1SAT (all clauses have size 1) is also NP-complete.

4. Given that PARTITION problem (described below) is a NP-Complete problem, prove
that the SUM OF SUBSETS problem (described below) is NP-Complete by reducing
PARTITION problem to it.

PARTITION:

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’ = Sum of all numbers in Z-Z’

SUM OF SUBSETS:

Instance: A finite set of positive integers A = { a1, a2, … , am } and M.
Question: Is there a subset A’ in A s.t.  ai = M?

ai in A’

(a) Give a nondeterministic polynomial time algorithm for the SUM OF SUBSETS
problem.

(b) Define the transformation from the PARTITION problem to the SUM OF SUBSETS
problem.

(c) Explain that the transformation described in part (b) satisfies: if the partition problem
has a solution then the sum-of-subsets has a solution, and vice versa.

5. Prove that the 0/1 KNAPSACK problem is NP-Hard. (One way to prove this is to
prove the decision version of 0/1 KNAPSACK problem is NP-Complete. In this problem,
we use PARTITION problem as the source problem.)

(a) Give the decision version of the O/1 KNAPSACK problem, and name it as DK.

(b) Show that DK is NP-complete (by reducing PARTITION problem to DK).

(c) Explain why showing DK, the decision version of the O/1 KNAPSACK problem, is
NP-Complete is good enough to show that the O/1 KNAPSACK problem is NP-hard.


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


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

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


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

blank

发表评论