\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}
\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\arc}[2]{#1 \rightarrow #2}
\newcommand{\size}[1]{\left|#1\right|}
\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}

\begin{document} 
\inclassproblems{5, Wed.}                    % !! start the paper

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

\begin{problem}
\begin{theorem*}
A graph $G$ is bipartite if and only if it contains no odd cycle.
\end{theorem*}

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

Your text alone should form a complete argument!

\bparts

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

\solution[\vspace{2in}]{First, we assume that $G$ is bipartite and
prove that $G$ contains no odd cycle.  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$ even 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.  We can make the same argument for any cycle in $G$, so every
cycle has even length.}

\ppart Now assume the right side.  As a first step toward proving the
left side, explain why we can focus on a single connected component
$H$ within $G$.

\solution[\newpage]{Next, we assume that $G$ contains no odd
cycle and prove that $G$ is bipartite.  If we can 2-color every
connected component of $G$, then we can 2-color all of $G$.  Thus, it
suffices to show that an arbitrary connected component $H$ of $G$ is
2-colorable.}

\ppart Let $T$ be a spanning tree of $H$.  Describe a 2-coloring of
$H$ based on this tree.

\solution[\vspace{2.5in}]{Let $T$ be a spanning tree of $H$.  Select a
root vertex $v$ arbitrarily.  Color a vertex $w$ red if the distance
to $v$ is even, and color $w$ black if the distance to $v$ is odd.}

\ppart Now we must prove that the coloring is valid.  Why must an edge
in the spanning tree connect different-colored vertices?  Why must an
edge {\em not} in the tree connect different-colored vertices?

\solution[\newpage]{Now we show that every edge in $H$ joins
differently-colored vertices.

First, consider an edge $\edge{x}{y}$ in the spanning tree.  Either
the unique path from $v$ to $y$ goes through $x$ or the unique path
from $v$ to $x$ goes through $y$.  In either case, one vertex is at an
odd distance from $v$ and the other is at an even distance from $v$,
so the two vertices are differently-colored.

Next, consider an edge $\edge{x}{y}$ not in the spanning tree.  Let
$z$ be the first common vertex on the path from $x$ to the root $v$
and the path from $y$ to $v$.  The paths from $x$ to $z$ and $y$ to
$z$ must have different parities (one odd, the other even); otherwise,
these two paths together with the edge $\edge{x}{y}$ would form an odd
cycle.  Therefore, $x$ and $y$ must be colored differently.

Therefore, the 2-coloring is valid and the graph is bipartite.}
\eparts

\end{problem}

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

\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.)

\begin{problemparts}

\problempart 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[\newpage]{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:

\mfigure{5in}{!}{register1}
}

\problempart 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[\vspace{3in}]{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.}

\problempart 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[\newpage]{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.
}

\end{problemparts}

\end{problem}

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

\begin{problem}
Here is a suggestive diagram related to binary DeBruijn sequences of
order \underline{three}.

\mfigure{!}{3in}{debruijn}

\bparts

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

\solution[\vspace{2in}]{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$.}

\ppart Do base-$n$ DeBruijn sequences of order $k$ exist for all $n, k
\geq 2$?  Explain your answer.

\solution{Yes.  We could repeat the contruction described above where
each varialbe $b_i$ denotes a base-$n$ number.  Each vertex has
indegree $n$ and outdegree $n$.  Thus, the digraph has an Euler tour
and there is a corresponding DeBruijn sequence.}

\eparts

\end{problem}

\end{document}
