Algorithm Design Techniques

 COMP-360              Assignment 4         Due: Tues,  April 1  in class

Late assignments  -10% per day, including weekends.

If you work closely with someone else, indicate the person's name(s) on your homework.
The final write-up of each assignment must, however, be your own work.

In NP-completeness proofs, you may assume that SAT, 3-SAT, IND SET, VERTEX COVER, and SUBSET SUM are known to be NP-complete.

1.  CLIQUE: Input: Graph G=(V,E), integer k.
Question: Is there a subset S of V with |S|=k such that every pair of vertices in S is joined by an edge in E?

(a) Show this problem is NP.
(b) Give a direct reduction from SAT(Text, P. 460)  to CLIQUE, and prove its correctness.
(c) Illustrate your reduction by constructing the CLIQUE input corresponding to the SAT input:

                    (x1 + x2 )(x1 + x2 + x3 + x4)(x2 + x3)(x2 + x3 +x4)

2.  Text, P. 505 problem 3. Hint: The problem is NP-complete even if each sport is known by exactly two councillors.
Also show how to formulate the original problem as an integer program.

3.  Review text pp. 266-271 which shows how to solve the SUBSET SUM problem by dynamic programming.
In class we reduced 3-SAT to SUBSET SUM. Explain in detail why these two results do not imply that P=NP.

4.  3-SCHED: Input: The processing times t1 , t2, ... , tn of n jobs, and a deadline T. All data are integers.
Each of the jobs must be scheduled on one of three identical machines. Each machine can process one job at a time.
Question: Is there a schedule so that all jobs finish before time T?

(a) Show that 3-SCHED is NP-complete.
(b) Show how to formulate  the problem of finding the smallest T for which there exists a 3-SCHED as an integer program.
(c) Use lp_solve to solve part (b) for the 9 jobs with processing times 104, 121, 145, 147, 150, 166, 168,  191, 194.