CompSci 163/265, Spring 2015, Homework 6

  1. For any integer $k$, define the $k$-bit binary graph $Q_k$ 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.

    1. Find a Hamiltonian cycle in $Q_3$. (You may report your answer by giving the sequence of binary strings in the cycle.)

    2. For which values of $k$ does $Q_k$ have an Euler tour, starting and ending at the same point?

    3. For which values of $k$ does $Q_k$ have an Euler path that starts and ends at two different vertices?

  2. 163 only:

    Find a weighted undirected graph for which the MST-doubling heuristic can generate a tour that is longer than optimal by a factor of at least $5/3$. Show both the optimal tour and the MST-doubling tour for your example. (You may use the simplest version of MST-doubling, without shortcutting repeated vertices.)

    263 only:

    Find a weighted undirected graph for which Christofides' heuristic can generate a tour that is longer than optimal by a factor of at least $4/3$. Show both the optimal tour and the Christofides tour for your example.

  3. Suppose that we know how to solve problem X in time $O(4^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.

    1. 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)?

    2. 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. 163 only:

    Recall that in class we went through a dynamic programming algorithm to compute $L(S,v)$, the length of the shortest path that starts at vertex $0$, ends at vertex $v$, and covers all the vertices in set $S$, using the equation $$L(S,v)=\min_{w\in S} L(S-v,w) + d(w,v).$$ Here $S-v$ denotes the set formed from $S$ by removing $v$, and $d(w,v)$ is the shortest path distance. Recall also that the length of the optimal traveling salesman tour is $$\min_v L(V,v)+d(v,0)$$ where $V$ is the set of all vertices in the graph. Give pseudocode that takes as input the already-computed array $L$ and uses these equations to backtrack through the array and find the optimal tour itself.

    263 only:

    If the $n$ vertices of a graph are assigned numbers from $0$ to $n-1$, then we can define the length of any edge to be the difference between the numbers of its endpoints, and define the total length of the numbering to be the sum of all the edge lengths. For instance, if a five-vertex and five-edge graph is numbered so that there are edges $0$–$1$, $0$–$3$, $1$–$2$, $2$–$3$, and $3$–$4$, then the total length is $1+3+1+1+1=7$. Give a dynamic programming algorithm to find the minimum possible total length of any numbering of a given graph. Your algorithm should take time within a polynomial factor of $2^n$.