Algorithm Design Techniques
Due: April 13, 2004
Assignments are to be left in the box near the labs,
McConnell 1st floor.
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.
For this assignment, you may use the fact that the following problems are
to be NP-complete: SAT, 3-SAT(also called 3-CNF-SAT), SUBSET SUM.
1. (a) Give a direct reduction of the 3-SAT problem to the VERTEX
the graph that you obtain from the expression: ( x + y + z ) . ( x + y+ z
) .(x+ y + z ) . ( x + y + z)
Find a satisfying truth assignment
and show on the grapht that it corresponds to a vertex cover of the same size.
(b) Illustrate the reduction from 3-SAT to SUBSET SUM (Cormen
pp1014-6) using the expression ( x
+ y + z ) . ( x + y+ z ) .(x+ y + z ) . ( x + y + z)
by building a table as
in Fig 34.19. Also write out all the numbers for the subset problem in decimal.
Show the equivalence between
two different satisying truth assignments and valid subset sums, using the
decimal representation of the numbers.
2. 3-Partition: Instance: Non-negative integers a1 , a2
, ... , an
Question: Can the integers
be partitioned into three disjoint
subsets of equal weight?
Show 3-Partition is NP-complete.
3. (a) Formulate the following problems as integer
linear programs: 3-SAT, VERTEX COVER, SUBSET SUM.
(b) Use lp_solve to find an integer programming solution
to the example of each of these problems given in question 1.