2023年11月25日

算法代写 | CIS2344 Assignment Specification (Logbook)

本次美国代写是一个Java高级算法设计和分析的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.