Carnegie Mellon University, Computer Science Department
Graduate Algorithms 15-750, Spring 2004,  
Instructor: Manuel Blum
TA: Doru Balcan

  
Homework Assignment #6

Important Note: Each problem is worth 10 points. The solutions 
are expected by Wednesday, Apr 28, at the beginning of the class 
(IN CLASS). 

MORE IMPORTANT NOTE:
This homework is NOT mandatory. We are aware of your efforts
towards the completion of the semester (due to assignments, project
deadlines, and the kind). Still, this may be an opportunity for 
those people who wish to raise their HW score, as well as for 
anyone who wants to keep in shape for the Final. 




1. Consider the following variant of the travelling salesman
problem, called the bottleneck TSP problem. The goal is to find 
a Hamiltonian tour of the input graph so as to minimize the length
of the LONGEST edge in the tour. Assuming that the input graph
satisfies the triangle inequality, show that this problem has 
a polynomial time approximation with ratio 3. [Actually, this
is Pb 1-2, pp.36, in Motwani's Approx. Algs. notes.]

  Extra Credit: Can you give an algorithm (i.e. a polynomial time,
approximation algorithm) having a ratio of 2? What about a ratio 
strictly smaller that 2? 





2. Random Walking on an orthogonal grid in d dimensions was 
introduced in class. Namely, we start from the origin, we take 
a unit step along a random direction (parallel to one of the axes), 
and we ask: how often can we hope to return to the origin?

  i) When d=1, what is the probability of returning to the origin,
in a number S of steps?

 ii) When d=2, what is p(S), the probability of returning to the origin 
after exactly S steps? 
     If we denote by p_1(S) the probability of lying on the first
coordinate axis after exactly S steps, and p_2(S) defined
analogously for the second coordinate axis, does there 

 p_1(S) * p_2(S) = p(S) ?


iii) (Extra Credit) For a general d, can you find an exact (i.e. 
closed-form) expression for the probability of returning to the 
origin after exactly S steps?
       




3. Consider the problem of deciding whether a polynomial with
integer coefficients, has (at least) a real root. Is this problem 
NP-complete? Does there exist a polynomial time (even randomized) 
algorithm that solves it?

Note: This the problem is trivial if we ask about complex roots,
instead of real.