%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[twoside,12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\problemset{5}{March 1, 2005}{Monday, March 7 at 9 PM in Room 32-044}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
An undirected graph $G$ has \term{width} $w$ if the vertices can be
arranged in a sequence
%
\[
v_1,\ v_2,\ v_3,\ \ldots,\ v_n
\]
%
such that each vertex $v_i$ is joined by an edge to at most $w$
preceding vertices.  (Vertex $v_j$ \textit{precedes} $v_i$ if $j <
i$.)  Use induction to prove that every graph with width at most $w$
is $(w + 1)$-colorable.

(Recall that a graph is \textit{$k$-colorable} iff every vertex can be
assigned one of $k$ colors so that adjacent vertices get different
colors.)
\end{problem}

\solution{We use induction on $n$, the number of vertices.  Let $P(n)$
be the proposition that every graph with width $w$ is $(w+1)$
colorable.

\noindent \textit{Base case:} Every graph with $n = 1$ vertex has
width 0 and is $0 + 1 = 1$ colorable.  Therefore, $P(1)$ is true.

\noindent \textit{Inductive step:} Now we assume $P(n)$ in order to
prove $P(n+1)$.  Let $G$ be an $(n+1)$-vertex graph with width $w$.
This means that the vertices can be arranged in a sequence
%
\[
v_1, v_2, v_3, \ldots, v_n, v_{n+1}
\]
%
such that each vertex $v_i$ is connected to at most $w$ preceding
vertices.  Removing vertex $v_{n+1}$ and all incident edges gives a
graph $G'$ with $n$ vertices and width at most $w$.  (If original
sequence is retained, then removing $v_{n+1}$ does not increase the
number of edges from a vertex $v_i$ to a preceding vertex.)  Thus,
$G'$ is $(w+1)$-colorable by the assumption $P(n)$.  Now replace
vertex $v_{n+1}$ and its incident edges.  Since $v_{n+1}$ is joined by
an edge to at most $w$ preceding vertices, we can color $v_{n+1}$
differently from all of these.  Therefore, $P(n+1)$ is true.

The theorem follows by the principle of induction.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
In this problem, we walk you through a proof of the following theorem:

\begin{theorem}\label{th:bip}
A graph $G$ is bipartite if and only if it contains no odd cycle.
\end{theorem}

\noindent As is common with ``if and only if'' assertions, the proof
has two parts.  Part (a) asks you to prove that the left side implies
the right side.  Parts (b), (c) and (d) help you prove that the right
side implies the left.

(Recall that a graph is \textit{bipartite} iff it is 2-colorable.)

\bparts

\ppart Assume the left side and prove the right side.  Three to five
sentences should suffice.

\solution{Select a 2-coloring of $G$.  Consider an arbitrary cycle
with vertices $v_1, v_2, \ldots, v_k$.  Then the vertices $v_i$ must
be one color for all even $i$ and the other color for all odd $i$.
Since $v_1$ and $v_k$ must be colored differently, $k$ must be even.
Thus, the cycle has even length.}

\ppart Now we're going to prove that the right side implies the left.
As a preliminary step, explain why there is a 2-coloring of any tree
$T$.

\solution{Select a ``root'' vertex $r$ arbitrarily.  Color a vertex
$v$ red if the distance in $T$ from $r$ to $v$ is even, and color $v$
black if the distance from $r$ is odd.

To see that this defines a valid 2-coloring of the tree $T$, consider
an arbitrary edge $\edge{x}{y}$.  There is a unique path from $x$ to
$r$ and a unique path from $y$ to $r$.  One of these paths must
contain the edge $\edge{x}{y}$; otherwise, this edge together with
portions of the other two paths would form a cycle.

If $\edge{x}{y}$ is on the unique path from $x$ to $r$, then $y$ is
exactly one edge closer than $x$ to the root $r$.  Similarly, if
$\edge{x}{y}$ is on the unique path from $y$ to $r$, then $x$ is one
edge closer than $y$ to the root.  In either case, one vertex is at an
odd distance from $r$ and the other is at an even distance from $r$,
so the two vertices are differently-colored.}

\ppart Suppose that $G$ is a \emph{connected} graph with no odd cycle,
and let $T$ be a spanning tree of $G$.  Show that a valid 2-coloring
of $T$ also defines a valid 2-coloring of $G$.

\solution{Vertices connected by an edge in $T$ have different colors
in a 2-coloring of $T$, so we need only show that an edge
$\edge{x}{y}$ \textit{not} in the tree must connect different-colored
vertices.

Let $z$ be the first common vertex on the path in $T$ from $x$ to the root
$v_0$ and the path in $T$ from $y$ to $v_0$.  The path from $x$ to $z$,
followed by the path from $z$ to $y$, followed by the edge $\edge{y}{x}$
form a cycle which, by hypothesis, must be of even length.  Since the
length of the cycle is one plus the sum of the lengths of the two paths,
one of the paths must have odd length and the other even length.  This
implies that of the paths from $x$ to $v_0$ and from $y$ to $v_0$, one has
even length and the other odd length.  From the way we 2-colored $T$, it
follows that $x$ and $y$ must be colored differently.}

\ppart Now assume the right side of Theorem~\ref{th:bip}; namely, $G$
is a graph with no odd cycle, but is not necessarily connected.  Prove
that $G$ is bipartite.

\solution{Color each connected component of $G$ with 2 colors one at a
time.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Let $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ be undirected graphs in
which every vertex has degree 1.  The \textit{union} of graphs $G_1$
and $G_2$ is the graph $G = (V, E_1 \cup E_2)$.  Prove that $G$ is
bipartite.
\end{problem}

\solution{Consider any cycle in $G$.  If an edge on the cycle is in
$E_1$, then the edges on either side in the cycle must be in $E_2$;
otherwise, the degree of $G_1$ would be greater than 1.  Thus, the
edges around the cycle are alternately in $E_1$ and $E_2$.  This
implies the length of the cycle must be even, so $G$ is bipartite by
Theorem~\ref{th:bip}.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
For each integer $n \geq 0$, we can define a graph called an {\em
$n$-cube}, which is denoted $H_n$.  The vertices are all $n$-bit
sequences, $\set{0, 1}^n$.  There is an edge between two vertices if
they differ in exactly one bit position.
%
\begin{center}
\includegraphics[height=1.25in]{ps4-ncubes}
\end{center}

\bparts

\iffalse
\ppart Prove that $H_n$ is bipartite for all $n$.

\solution{We prove that the $n$-cube is bipartite by describing an
explicit 2-coloring.  Each vertex is an $n$-bit sequences, $b_1 b_2
\ldots b_n$.  Color a vertex red if $b_1 + b_2 + \ldots + b_n$ is
even, and color the vertex blue if the sum is odd.  Since adjacent
vertices differ in exactly one bit, one must have an even sum and the
other an odd sum.  Therefore, the endpoints of every edge are colored
differently.}

\fi

\ppart Prove that $H_n$ has an Euler tour for all even $n \geq 2$.

\solution{We prove that $H_n$ has an Euler tour by showing that it is
connected and every vertex has even degree.

First, consider two arbitrary vertices in an $n$-cube, $b_1 b_2 \ldots
b_n$ and $c_1 c_2 \ldots c_n$.  These two vertices are joined by a
path which traverses the distinct vertices in the following sequence:

\[
\begin{array}{c}
b_1 b_2 b_3 \ldots b_n \\
c_1 b_2 b_3 \ldots b_n \\
c_1 c_2 b_3 \ldots b_n \\
\ldots \\
c_1 c_2 c_3 \ldots c_n \\
\end{array}
\]

Therefore, the graph is connected.

Each vertex $v$ in an $n$-cube is adjecent to exactly $n$ other
vertices, those which can be obtained by flipping one of the $n$ bits
of vertex $v$.  Therefore, if $n$ is even, every vertex in an $n$-cube
has even degree.  Thus, $H_n$ has an Euler tour for all even $n \geq
2$.}

\ppart Prove that $H_n$ has a Hamiltonian cycle for all $n \geq 2$.
Consider an inductive argument based on the fact that $H_{n+1}$
consists of two subgraphs isomorphic to $H_n$ (bold lines) with
corresponding vertices joined (dotted lines):
%
\begin{center}
\includegraphics[height=1.25in]{ps4-ncube-construction}
\end{center}

\solution{We use induction on $n$.  Let $P(n)$ be the proposition that
an $n$-cube has a Hamiltonian cycle.  A $2$-cube is itself a cycle on
four vertices, so $P(2)$ is true.  Now suppose that $P(n)$ is true for
some $n \geq 2$, and consider an $(n+1)$-cube.  As noted in the
suggestion, this graph consists of two subgraphs isomorphic to the
$n$-cube, with corresponding vertices joined by edges.  By induction,
there is a Hamiltonian cycle $C_n$ in one of these two subgraphs and a
corresponding Hamiltonian cycle $C_n'$ in the other.  Deleting an edge
$\edge{u}{v}$ from $C_n$, deleting the corresponding edge $\edge{u'}{v'}$
from $C_n'$, and adding the edges $\edge{u}{u'}$ and $\edge{v}{v'}$
creates a Hamiltonian cycle in the $(n+1)$-cube.  Therefore, $P(n+1)$
is true, and the claim follows by the principle of induction.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse

\begin{problem}
Scholars through the ages have identified {\em twenty} fundamental
human virtues: honesty, generosity, loyalty, prudence, volunteering
for 6.042 demonstrations, etc.  At the beginning of the term, every
student in 6.042 possessed exactly {\em eight} of these virtues.
Furthermore, every student was unique; that is, no two students
possessed exactly the same set of virtues.  The 6.042 course staff
must select {\em one} additional virtue to impart to each student by
the end of the term.  Prove that there is a way to select an
additional virtue for each student so that every student is unique at
the end of the term as well.

\noindent Suggestion: Use Hall's theorem.  Try various interpretations
for the vertices on the left and right sides of your bipartite graph.

\solution{Construct a bipartite graph $G$ as follows.  The vertices on
on the left are all students and the virtues on the right are all
subset of nine virtues.  There is an edge between a student and a set
of 9 virtues if the student already has 8 of those virtues.

Each vertex on the left has degree 12, since each student can learn
one of 12 additional virtues.  The vertices on the right have degree
at most 9, since each set of 9 virtues has only 9 subsets of size 8.

Therefore, by the special case of Hall's Theorem proved in the
in-class problems on Friday, there is a matching for the students.
Thus, if each student is taught the additional virtue in the set of 9
virtues with whom he or she is matched, then every student is unique
at the end of the term.
}

\end{problem}

\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
A portion of a computer program consists of a sequence of calculations
where the results are stored in variables, like this:

\[
\begin{array}{rrrcl}
&& \text{Inputs:} &  & a, b \\
\text{Step } 1. & \hspace{0.5in} & c & = & a + b \\
2. && d & = & a * c \\
3. && e & = & c + 3 \\
4. && f & = & c - e \\
5. && g & = & a + f \\
6. && h & = & f + 1 \\
&& \text{Outputs:} & & d, g, h
\end{array}
\]

A computer can perform such calculations most quickly if the value of
each variable is stored in a {\em register}, a chunk of very fast
memory inside the microprocessor.  Computers usually have few
registers, however, so they must be used wisely and reused often.  The
problem of assigning each variable in a program to a register is
called {\em register allocation}.

In the example above, variables $a$ and $b$ must be assigned different
registers, because they hold distinct input values.  Furthermore, $c$
and $d$ must be assigned different registers; if they used the same
one, then the value of $c$ would be overwritten in the second step and
we'd get the wrong answer in the third step.  On the other hand,
variables $b$ and $d$ may use the same register; after the first step,
we no longer need $b$ and can overwrite the register that holds its
value.  Also, $f$ and $h$ may use the same register; once $f + 1$ is
evaluated in the last step, the register holding the value of $f$ can
be overwritten.

(Assume that the computer carries out each step in the order listed
and that each step is completed before the next is begun.)

\bparts

\ppart Recast the register allocation problem as a question
about graph coloring.  What do the vertices correspond to?  Under what
conditions should there be an edge between two vertices?  Construct
the graph corresponding to the example above.

\solution{There is one vertex for each variable.  An edge between two
vertices indicates that the values of the variables must be stored in
different registers.

We can classify each appearance of a variable in the program as either
an {\em assignment} or a {\em use}.  In particular, an appearance is
an assignment if the variable is on the left side of an equation or on
the ``Inputs'' line.  An appearance of a variable is a use if the
variable is on the right side of an equation or on the ``Outputs''
line.

The {\em lifetime} of a variable is the segment of code extending from
the initial assignment of the variable until the last use.  There is
an edge between two variables if their lifetimes overlap.  This rule
generates the following graph:
%
\begin{center}
\includegraphics[width=5in]{register1}
\end{center}
}

\ppart Color your graph using as few colors as you can.  Call
the computer's registers $R1$, $R2$, etc.  Describe the assignment of
variables to registers implied by your coloring.  How many registers
do you need?

\solution{Four registers are needed.  One possible assignment of
variables to registers is indicated in the figure above.

In general, coloring a graph using the minimum number of colors is
quite difficult; no efficient procedure is known.  However, the
register allocation problem always leads to an {\em interval graph}.
For interval graphs, there are efficient coloring procedures, which
can be incorporated into a compiler.}

\ppart Suppose that a variable is assigned a value more than
once, as in the code snippet below:
%
\begin{eqnarray*}
  & \ldots & \\
t & = & r + s \\
u & = & t * 3 \\
t & = & m - k \\
v & = & t + u \\
  & \ldots &
\end{eqnarray*}
%
How might you cope with this complication?

\solution{Each time a variable is reassigned, we could regard it as a
completely new variable.  Then we would regard the example as
equivalent to the following:
%
\begin{eqnarray*}
  & \ldots & \\
t & = & r + s \\
u & = & t * 3 \\
t' & = & m - k \\
v & = & t' + u \\
  & \ldots &
\end{eqnarray*}
%
We can now proceed with graph construction and coloring as before.
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
A \term{DeBruijn sequence of order $k$} is a string of $0$'s and $1$'s
that contains every combination of $k$ bits as a substring exactly
once.  For example, here is a DeBruijn sequence of order 2:
%
\[
01100
\]
%
Notice that every combination of two bits (01, 11, 10, and 00) appears
exactly once as a substring.

\bparts

\ppart Find a DeBruijn sequence of order 3.  You may find the
following diagram helpful.
%
\begin{center}
\includegraphics[height=3in]{debruijn}
\end{center}

\solution{One possible solution is:
%
\[
1000101110
\]
%
Notice that this correponds to a directed walk that traverses every
edge exactly once.}

\ppart In a directed graph, a \textit{directed walk} is an alternating
sequence of vertices and edges:
%
\[
v_1, \arc{v_1}{v_2}, v_2, \arc{v_2}{v_3}, v_3, \arc{v_3}{v_4},
v_4, \ldots, v_{n-1}, \arc{v_{n-1}}{v_n}, v_n
\]
%
A \textit{directed Euler tour} is a directed walk that traverses every
edge in a graph exactly once and ends where it began; that is, $v_1 =
v_n$.  Suppose $G$ is a directed graph such that the in-degree of each
vertex is equal to its out-degree and there is a directed walk from
every vertex to every other vertex.  Prove that $G$ has a directed
Euler tour.

\solution{We use proof by contradiction.  Let
%
\[
P = \arc{v_1}{v_2}, \arc{v_2}{v_3}, \arc{v_3}{v_4}, \ldots, \arc{v_{n-1}}{v_n}
\]
%
be the longest directed path in $G$.  Then every edge out of $v_n$
must be on the path.  Since the indegree of $v_n$ is equal to the
out-degree, the only possibility that the $v_1 = v_n$.

Suppose that $P$ is \textit{not} a directed Euler tour; that is, some
edge $\arc{x}{y}$ in graph $G$ is not on the path $P$.  Then there
exists a directed path from $v_1$ to $x$ by assumption.  Let
$\arc{v_i}{z}$ be the first edge on this path that is not on the path
$P$.  Then the directed path
%
\[
\arc{v_i}{v_{i+1}}, \arc{v_{n-1}}{v_n}, \arc{v_1}{v_2}, \arc{v_2}{v_3}, \ldots, \arc{v_i}{z}
\]
%
is longer than $P$, which is a contradiction.}

\ppart Explain why a DeBruijn sequence of order $k$ exists for every
$k \geq 2$.

\solution{Construct a digraph whose vertices are all $(k-1)$-bit
strings.  Put a directed edge labeled $b_k$ from each vertex $b_1 b_2
\ldots b_{k-1}$ to the vertex $b_2 \ldots, b_{k-1} b_k$.  (Here, each
variable $b_i$ denotes a bit.)  Each vertex has indegree 2 and
outdegree 2.  Therefore, the digraph has an Euler tour.  The labels on
the edges in the tour form a binary DeBruijn sequence of order $k$.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
