Assignment #2 SOlution

Please upload your submission as a single PDF le on D2L. If your submission consists of more than one le, convert all your les into a single PDF le and upload it.







Assuming P 6= NP, for each of the problems below, say whether it is solvable in polynomial time or whether it is NP-complete, and justify your answer. (That is, if you say that the problem is polynomial-time solvable, explain how it can be solved in polynomial time; and if you say that it is NP-complete, give a polynomial-time reduction from an NP-complete problem to it.)



Given n coins of two di erent denominations (values), that is some coins are worth x dollars and some are worth y dollars, decide if the coins can be partitioned into two parts that have the same monetary value.



Given n checks, each of arbitrary (integer) monetary value, decide if the checks can be partitioned into two parts that have the same monetary value.



Given an undirected graph G, decide if G has an independent set of 5 vertices.



Illustrate the execution of Merge Sort on the array A = h6; 4; 9; 8; 5; 10; 1; 3i. Regarding the level of illustration, follow the level of illustration done



in class but complete the illustration until the end (array is sorted).







Illustrate the execution of Quick Sort on the array A = h6; 4; 9; 8; 5; 10; 1; 3i. Please use the version of Quick Sort discussed in class, which is the same as the one covered in the textbook. Regarding the level of illus-tration, follow the level of illustration done in class but complete the illustration until the end (array is sorted).



Suppose that we are given an array A[1::n] of integers such that



A[1] < A[2] < : : : < A[n]. Give an O(lg n) time algorithm to decide if there exists an index 1 i n such that A[i] = i.




Textbook, pages 39-40, problem 2-1, parts a, b, and c.