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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{3}                    % !! start the paper

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


\begin{problem}

Let $L_n$ be the $(n+1)$-vertex {\em line graph}, which consists of a
single simple path of length~$n$.  For example, here is $L_4$:

\bigskip
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}
\bigskip
\centerline{The line graph $L_4$.}
\bigskip

A graph is {\em two-ended} if it has exactly two vertices of degree
one and all other vertices have degree two.  Note that $L_n$ is a
two-ended graph for every $n \geq 1$.  Consider the following false
theorem.

\paragraph{False theorem:}
Every two-ended graph with $n$ edges is isomorphic to~$L_n$.

\begin{problemparts}

\problempart Draw a diagram of the smallest two-ended graph that is
{\em not} isomorphic to a line graph.

\solution{
Here is the smallest counterexample:

\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}
\end{center}}

\problempart Explain briefly, but clearly, where the following proof
goes wrong:

\paragraph{False proof:}
We prove the thorem by induction on $n$, the number of edges in the
graph, with the hypothesis that every two-ended graph with $n$ edges
is isomorphic to $L_n$.

(Base case, $n = 1$): A simple graph with one edge can have only the
two vertices connected by that edge and some number of vertices not
attached to any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge consists of that edge and the two
vertices it joins, which makes it isomorphic to~$L_1$.

(Inductive step): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Let $G_n$ be any two-ended graph
with $n$ edges.  By hypothesis, $G_n$ is isomorphic to~$L_n$.  Suppose
an edge is added to~$G_n$ to form a two-ended graph~$G_{n+1}$.  Since
$G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  Thus, the resulting $(n+1)$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.

The theorem follows by induction.

\solution{The first definite error is in the final line; the theorem
does {\em not} follow by the principle of induction.  However, the
proof goes astray earlier, in the inductive step.  While {\em
something} is correctly proved in the inductive step, it is not what
{\em should} be proved in order to invoke the induction principle on
the last line.

More precisely, in the inductive step, we may assume that:

\begin{quote}
{\em Every two-ended graph with $n$ edges is isomorphic to $L_n$.}
\end{quote}

And then we must prove that:

\begin{quote}
{\em Every two-ended graph with $n+1$ edges is isomorphic to $L_{n+1}$.}
\end{quote}

But this is not proved in the inductive step of the false proof.  Oh,
no.  What we actually prove is that:

\begin{quote}
{\em Every two-ended graph with $n+1$ edges \underline{which can be
obtained by adding a single edge to $L_n$} is isomorphic to
$L_{n+1}$.}
\end{quote}

This is a much weaker statement, because there exist two-ended graphs
with $n+1$ edges that can {\em not} be obtained by adding a single
edge to $L_n$.  For example, the graph shown in part (a) is a
two-ended graph with 5 edges that can not be obtained by adding a
single edge to $L_4$.}

\end{problemparts}

\end{problem}


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

\begin{problem}
Suppose that 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{There is one vertex for each variable.  And edge between two
vertices indicates that the values of the variables must be stored in
different registers.

There is an edge between every pair of vertices corresponding to input
variables.  In addition, we can classify each appearance of a variable
in the program as either an ``assignment'' or a ``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.  We put an edge between variable
$u$ and variable $v$ if $u$ is assigned on a line between an
assignment and use of $v$.  This situation is illustrated below:

\[
\begin{array}{rclll}
v & = & ??? & \hspace{0.5in} & \text{// assignment of $v$} \\
  & \ldots & \\
u & = & ??? & & \text{// assignment of $u$} \\
  & \ldots & \\
? & = & v + ? & & \text{// use of $v$}
\end{array}
\]

For the example above, these rules generate the following graph:

\bigskip
\centerline{\includegraphics[width=5in]{register1}}
\bigskip
}

\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{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 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.
}

\end{problemparts}

\end{problem}

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


\begin{problem}
A {\em game tree} is a finite, rooted tree in which every leaf is
labeled with a real number, which is called a {\em payoff}.

There is a {\em tree game} associated with every game tree.  At every
step of the game, there is a {\em current vertex}.  Initially, the
current vertex is the root of the tree.  The two players alternate
turns.  On each player's turn, he or she must select a child of the
current vertex to become the new current vertex.  The game ends when a
leaf is reached.  The second player should now pay the first player
$p$ million dollars, where $p$ is the payoff at the leaf.  Note that a
negative payoff benefits the second player at the expense of the
first.

\begin{problemparts}

\problempart If both players make the best possible moves, what is the
payoff?  This is called the {\em value} of the game.

\solution{The first player receives a payoff of 3 million dollars.}

\problempart Which of the following conventional games is equivalent
to a tree game on some suitable game tree?  For each game below,
assume that the winner is paid one million dollars by the loser and
that no money changes hands in a draw.

\begin{itemize}

\item Tic-Tac-Toe

\item Battleship

\item Chess

\item Backgammon

\end{itemize}

\solution{Tic-Tac-Toe and Chess are tree games corresponding to
certain very large game trees.  (The rules of chess guarantee that
every game eventually terminates, which ensures that the tree is
finite.)  Battleship is not a tree game, because each player has
information that the other lacks.  Backgammon is not a tree game,
because moves involve a degree of randomization.  There do exist more
general types of game tree that model both hidden information and
randomization.}

\problempart Suppose that Alice and Bob play a tree game, and the
payoffs at the leaves indicate {\em how much Bob pays Alice},
regardless of who goes first.  Thus, Alice is trying to maximize the
payoff, and Bob is trying to minimize the payoff.

Prove that every tree game has a {\em value} determined by which of
the two players goes first.  More precisely, prove that for every game
tree and choice of first player, there exists a value $v$ such that
Alice can guarantee a payoff of at least $v$ and Bob can guarantee a
payoff of at most $v$.

\solution{The proof is by strong induction on the number of vertices
in the game tree.  Let $P(n)$ be the proposition that for every
$n$-vertex game tree and and choice of first player, there exists a
value $v$ such that Alice can guarantee a payoff of at least $v$ and
Bob can guarantee a payoff of at most $v$.

For the base case, consider a game tree consisting of a single vertex.
Let $v$ be the payoff of this vertex.  Then, regardless of who goes
first, Alice can guarantee a payoff of at least $v$ and Bob can
guarantee a payoff of at most $v$, since no other payoff is possible.

Now suppose that $P(1), \ldots, P(n)$ are true, and consider a game
tree $T$ with $n + 1$ vertices.  Let $T_1, \ldots, T_k$ be the
subtrees rooted at the children of $T$. 

Suppose that Alice goes first.  Let $b_1, \ldots, b_k$ be the values
of the tree games on $T_1, \ldots, T_k$ assuming that Bob goes first.
Let $b_i$ be the maximum of those values.  Then Alice can guarantee a
payoff of at least $b_i$ by selecting the $i$-th child.  On the other
hand, suppose that Alice selects the $j$-th child.  Then Bob can
guarantee that the payoff is at most $b_j \leq b_i$.  Thus, regardless
of what Alice does, Bob can guarantee that the payoff is at most
$b_i$.  Therefore, if Alice goes first, the game has value $b_i$.

If Bob goes first, the argument is a mirror image of the previous one.
Let $a_1, \ldots, a_k$ be the values of the tree games on $T_1,
\ldots, T_k$ assuming that Alice goes first.  Let $a_i$ be the minimum
of those values.  Then Bob can guarantee that the payoff is at most
$a_i$ by selecting the $i$-th child.  On the other hand, suppose that
Bob selects the $j$-th child.  Then Alice can guarantee a payoff of at
least $a_j \geq a_i$.  Thus, regardless of what Bob does, Alice can
guarantee a payoff of at least $a_i$.  Therefore, if Bob goes first,
the game has value $a_i$.

Therefore, $P(n+1)$ is true, and the theorem follows by induction.
}

\end{problemparts}

\end{problem}

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

\begin{problem}
Let $\Delta(G)$ denote the maximum degree of any vertex in the graph
$G$.

\begin{problemparts}

\problempart Prove that every graph $G$ can be colored with $\Delta(G)
+ 1$ colors.

\solution{The proof is by induction on the $n$, the number of vertices
in the graph $G$.  We take the induction hypothesis from the statement
of the claim.

First, suppose that $n = 1$; that is, the graph $G$ consists of a
single vertex.  Then $\Delta(G) = 0$, and $G$ can indeed be colored
with $\Delta(G) + 1 = 1$ color.

Now assume the claim holds for every graph with $n$ vertices, where $n
\geq 1$.  Let $G$ be a graph with $n + 1$ vertices.  Select a vertex
$v$ and remove it from $G$ to form a subgraph $G'$.  The graph $G'$
has $n$ vertices and maximum degree $\Delta(G') \leq \Delta(G)$.
Therefore, $G'$ can be colored with $\Delta(G) + 1$ colors.  Now add
vertex $v$ back to the graph.  Since $v$ has at most $\Delta(G)$
neighbors and there are $\Delta(G) + 1$ colors available, we can
assign $v$ a color not used by any of its neighbors.  This shows that
$G$ is $\Delta(G) + 1$ colorable.

The theorem follows by induction.
}

\problempart Give an example of a graph $G$ that can not be colored
with $\Delta(G)$ colors.

\solution{One example is a cycle with an odd number of vertices, such
as a pentagon.  This graph has maximum degree 2, but requires 3
colors.  Another example is the complete graph on $n$ vertices.  This
has maximum degre $n - 1$, but requires $n$ colors.}

\problempart A graph is {\em regular} if every vertex has the same
degree.  Show that if a graph $G$ is connected and not regular, then
it can be colored with $\Delta(G)$ colors.

\solution{The proof is by strong induction on the number of vertices.
Let $P(n)$ be the proposition that every connected, non-regular graph
$G$ with $n$ vertices can be colored with $\Delta(G)$ colors.

First, note that $P(1)$ is vacuously true, because there are no
non-regular graphs with 1 vertex.

Now assume that $P(1), \ldots, P(n)$ are true.  We must show that
$P(n+1)$ is true; that is, every connected, non-regular graph $G$ with
$n+1$ vertices can be colored with $\Delta(G)$ colors.  Since $G$ is
not regular, it has a vertex $v$ of degree less than $\Delta(G)$.
Remove that vertex to produce a graph $G'$.

Next, we show that $G'$ is $\Delta(G)$-colorable.  It suffices to show
that every connected component $C$ of the graph $G'$ is
$\Delta(G)$-colorable.  There are two cases:

\begin{enumerate}

\item Suppose that $C$ is regular.  Since $G$ was connected, vertex
$v$ was connected to at least one vertex in $C$.  Therefore, removing
$v$ reduced the degree of some vertex in $C$ to less than $\Delta(G)$.
Since $C$ is regular, all vertices in $C$ must have degree less than
$\Delta(G)$.  By part (a), $C$ is $\Delta(G)$-colorable.

\item Suppose that $C$ is not regular.  Then $\Delta(C) \leq
\Delta(G)$, and so $C$ is $\Delta(G)$-colorable by induction.

\end{enumerate}

Finally, we add the vertex $v$ back to $G'$ to obtain the original
graph $G$.  Since $v$ has fewer than $\Delta(G)$ neighbors and there
are $\Delta(G)$ colors available, we can assign $v$ a color not used
by any of its neighbors.  This shows that $G$ is $\Delta(G)$
colorable.  The theorem follows by induction.
}

\end{problemparts}

\end{problem}

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

\newpage

\centerline{{\LARGE A Game Tree}}

\vspace{0.5in}

\centerline{\includegraphics[width=6in]{gametree}}

\end{document}
