Description
1. 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.)
(a) Given n coins of two different 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.
(b) 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.
(c) Given an undirected graph G, decide if G has an independent set
of 5 vertices.
2. 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).
3. 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 illustration, follow the level of illustration done in class but complete the
illustration until the end (array is sorted).
4. 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.
5. Textbook, pages 39-40, problem 2-1, parts a, b, and c.
