Assignment 5: FFTs, NP and NP-Complete Problems
CSE 417: Algorithms and Computational Complexity
The University of Washington, Seattle, Winter 2013
The reading for this assignment is: (a) Section 5.6 and (b) Chapter 8 of Algorithm Design by Kleinberg and Tardos.

Do this assignment independently, without the use of online resources or collaboration.

Due Friday, March 15. Submit your answers as hardcopy at the beginning of class.
 
  1. Polynomial Evaluation (20 points). Consider the following polynomial:
    A(x) = 1 + 2x + 3x2 + 4x3
    Compute the discrete Fourier transform of [1, 2, 3, 4] by evaluating A(x) at the four fourth roots of unity:
    [ω , ω2 , ω 3, ω4]
    where ω equals the square root of -1. (You do not need to use the FFT here.)
     
  2. FFTs (20 points). Show a data-flow diagram containing the four "butterfly" steps for computing the Fast Fourier Transform of this same vector. Show, in your diagrams, what multiplication(s) and additions are performed, and what the outputs are from each butterfly for this example.
     
  3. Karp Reductions (20 points). Take the following instance A of 3-SAT and reduce it to an instance B of VERTEX-COVER 
    (x1 v x2' v x3) ^ (x1' v x3' v x4) ^ (x2 v x3' v x4') ^ (x2' v x3' v x4)
    1. Create B. (Construct the graph and specify the appropriate value of k.)
    2. Identify a vertex cover C of size at most k for B.
    3. From C, determine a satisfying assignment T for A.

     
  4. Certification for NP (20 points). (20 points) The 2D-PACKING problem is this: Given a bounded region R of the 2D cartesian plane, and a non-negative integer k, is it possible to pack the region with k or more tiles. Each tile is square (1 by 1) and can be positioned anywhere in the plane, provided its sides remain parallel to the x or y axes. The tiles in a packing may not overlap, and they must stay within the given region. A packing is maximal if there are as many tiles in it as possible.

    The following three illustrations give a packing region and two possible packings of it. The packing region is shown in white. Tiles are not allowed to go into the gray area. The first packing has only 2 tiles, whereas the other packing as 3 tiles. The tiles may fit "snuggly" into the packing region as they do here, but that is not required. For example, the packing region could have rounded or irregular boundaries.

    From these illustrations, we can see that the answers to some instances of packing problem with this region are: Yes for k=2 and Yes for k=3, but No for k > 3.

    The following example is somewhat similar, except that we see that a maximum packing here has only 2 tiles, and furthermore there are two possible maximal packings for this region.

    Prove that the 2D-PACKING problem is in NP.
     

  5. Matchings in higher dimensions (20 points). Do exercise 7 on p. 507.
Updates and Corrections: The polynomial in Problem 1 was changed from A(x) = x3 + 2x2 + 3x + 4 on March 12. If you used the old version of A(x) and computed a discrete Fourier transform correctly using that polynomial, we will accept that answer.
Any additional changes or important clarifications to the assignment will be posted here. Last updated: March 12, 2013.