CS 163 / CS 265 Homework 6, due Friday, February 22

1. For any integer k, define the k-bit binary graph Qk by making 2^k vertices, one for each string of 0's and 1's of length k, and connecting two vertices by an edge whenever their strings differ from each other only in one position. Find a Hamiltonian cycle in Q3. (You may report your answer by giving the sequence of binary strings in the cycle.)

2. For which values of k does Qk have an Euler cycle? For which values of k does it have an Euler path that starts and ends at two different vertices?

3. Suppose that we know how to solve problem X in time O(3^n) on inputs with n vertices, but then Professor Bjorklund discovers an improved algorithm that takes time O(2^n). Also suppose that the constant factors in the two O-notations are the same and that both algorithms are limited by computation time rather than by memory or I/O complexity.

(a) What is the effect of Professor Bjorklund's improvement on the size of the largest problem that can be solved in at most one hour of computer time (on some particular computer)?

(b) If you ran Professor Bjorklund's algorithm on two computers, one of which is twice as fast as the other, what would be the effect of using the faster computer on the size of the largest problem that can be solved in at most one hour of computer time?

4. Consider the following idea for the traveling salesperson problem: sort the vertices by their distance from the first vertex, and visit them in sorted order from nearest to farthest. Does this have a finite approximation ratio (using shortest-path distances on arbitrary positively-weighted graphs as the inputs)? If so, what is it? If not, why not?

5* (CS265 only). Recall that the MST-doubling heuristic for the TSP achieves an approximation ratio of two using the following steps:
   (a) compute a minimum spanning tree
   (b) double its edges
   (c) compute an Euler tour of the doubled graph
   (d) shortcut repetitions of vertices from the tour
Suppose we decide to shortcut the algorithm, by instead performing the following simplified steps:
   (a) compute a minimum spanning tree
   (b) choose an arbitrary starting vertex
   (c) visit the vertices in the order of a preorder traversal of the tree
Does this still give an approximation ratio of two? Explain why or why not.