Homework C

This homework is due 2011-11-24, at 17.15. Drop it off by Mikael Goldmann's mailbox at Lindstedtsvägen 3.

The solutions must be printed, not handwritten. Solutions handed in late are not accepted and will not be graded.

It may be possible to Google solutions for some of these problems. Please do not do that.

Please remember that solutions need to be in English.

Problem 1 (5 pts)

Mulitply the following two polynomials using FFT.

x³ + 3x² + x - 1 and
2x³ - x² + 3

If you use a recursive version of FFT, you only need to show the top-most call to FFT (and FFT inverse), what recursive calls are made from the top-most level, what those calls return and how the final result is computed.

Problem 2 (5 pts)

Let A = (a_i,j) be a matrix such that a_i,j = a_i-1,j-1 and a_i,1 = a_i-1,n for i = 2, 3,...,n and j = 2, 3,...,n. Give an O(n log n)-time algorithm for computing Ax where x is a vector of length n

Problem 3 (5 pts)

Recall that integer linear programming is linear programming with the additional contraint that the variables are only allowed to take on integer values. In class we have seen how to formulate 3SAT as well as TSP as integer linear programs (with an exponential number of constraints in the case of TSP). Show how to formulate the Vertex Cover problem as an integer linear program (with a polynomial number of constraints).

Problem 4 (5 pts)

Give an example of Euclidian TSP where the nearest neighbor heuristic fails to find the optimal solution.

Problem 5 (5 (+2) pts)

Generalize the result for nearest neighbor (NN) as follows. Find a constant K > 1 and an increasing function f(n) such that, for each n there is a Euclidian TSP instance with f(n) cities for which NN, starting in city 1 will yield a solution that is at least K times larger than the optimum solution. You get 2 bonus points if K is such that Christofides' algorithm is guaranteed to do better on these instances.

Note. The purpose of the function f above is to give you a bit of freedom so that you do not need to provide a construction with n cities for every n. Rather, it is suffucient to provide a construction with, for example, 3n + 1 cities for all integers n > 0. By increasing we mean that f(n+1) > f(n) for all n.