\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\input{macros-course}

\newif\ifspaceout
\spaceouttrue
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{3in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}


\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}

\ifshowsolutions
\pquizsol{1}{October 12, 2000}
\else
\pquiz{1}{October 5, 2000}
\fi


\begin{problems}

\problem\pts{6} \textbf{Quantifiers}

Consider the following proposition.

\[
\forall x \forall y \ (x < y \rightarrow \exists z \ (x < z \wedge z < y))
\]

\begin{problemparts}

\problempart\pts{2}  Prove or disprove this proposition,
assuming that the universe is the set of integers.


\solution{ The proposition is false.  In the case where $x = 0$ and $y
= 1$, there does not exist an integer $z$ such that $x < z$ and $z <
y$.  }

\smallspace
\problempart\pts{4}   Write the negation of this proposition.
Your solution may {\em not} use the $\neg$ symbol, but may use any of
the relations $=$, $<$, $>$, $\leq$, or $\geq$.


\solution{
\[
\exists x \exists y \ (x < y \wedge \forall z \ (x \geq z \vee z \geq y))
\]
}

\end{problemparts}

\nextproblem
\problem\pts{10} \textbf{Induction}

Define the matrix

\begin{eqnarray*}
M & = & \left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right].
\end{eqnarray*}

Let $M^n$ denote the product of $n$ copies of the matrix $M$.  Use
ordinary induction to prove that for all $n \geq 1$, the upper right
entry of $M^n$ is $F_n$, the $n$-th Fibonacci number.  State your
inductive hypothesis clearly.

For reference, the standard formula for the product of $2 \times 2$
matrices is given below.

\begin{eqnarray*}
\left[
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right]
\cdot
\left[
\begin{array}{cc}
e & f \\
g & h
\end{array}
\right]
& = &
\left[
\begin{array}{cc}
ae + bg & af + bh \\
ce + dg & cf + dh
\end{array}
\right]
1g\end{eqnarray*}

Recall that $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, \ldots.

\solution{
\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that

\begin{eqnarray*}
M^n & = & \left[
\begin{array}{cc}
F_{n-1} & F_n \\
F_n & F_{n+1}
\end{array}
\right].
\end{eqnarray*}

In the base case, $P(1)$ is true because

\begin{eqnarray*}
M^1 & = & 
\left[
\begin{array}{cc}
0 & 1 \\
1 & 1
\end{array}
\right] \\
& = &
\left[
\begin{array}{cc}
F_0 & F_1 \\
F_1 & F_2
\end{array}
\right].
\end{eqnarray*}
\end{proof}

In the inductive step, for $n \geq 1$ assume $P(n)$ to prove $P(n+1)$.
The following equalities hold.

\begin{eqnarray*}
M^{n+1} & = &   M^n \cdot M \\
        & = &   \left[
                \begin{array}{cc}
                F_{n-1} & F_n \\
                F_n & F_{n+1}
                \end{array}
                \right] \cdot
                \left[
                \begin{array}{cc}
                0 & 1 \\
                1 & 1
                \end{array}
                \right] \\
        & = &   \left[
                \begin{array}{cc}
                F_n & F_{n-1} + F_n \\
                F_{n+1} & F_n + F_{n+1}
                \end{array}
                \right] \\
        & = &   \left[
                \begin{array}{cc}
                F_n & F_{n+1} \\
                F_{n+1} & F_{n+2}
                \end{array}
                \right]
\end{eqnarray*}

The first step uses the definition of $M^n$.  The second step uses the
induction hypothesis and the definition of the matrix $M$.  We carry
out a matrix multiplication in the third step and use the Fibonacci
recurrence in the last step.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
}

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




\nextproblem
\problem\pts{10}  \textbf{Structural Induction}

Consider the sets $S_1,S_2,\ldots$ defined inductively as
%
\begin{itemize}
\item $S_0 = \set{0,1}$
\item For all $n\geq 1$, $S_n = \set{\frac{x+y}{2}\ |\ x,y\in S_{n-1}}$
\end{itemize}
%
i.e., where $S_n$ contains the average values of each pair of numbers
in $S_{n-1}$.  Note we allow $x=y$ in the definition of $S_n$.

\bparts

\ppart \onept Write out the elements of each of the following sets: $S_1$,
$S_2$, and $S_3$.  

\solution{
  \begin{center}
    \begin{tabular}{rl}
      $S_1$ & $\set{0,1/2,1}$ \\
      $S_2$ & $\set{0,1/4,1/2,3/4,1}$ \\
      $S_3$ & $\set{0,1/8,1/4,3/8,1/2,5/8,3/4,7/8,1}$
    \end{tabular}
  \end{center}
}

\smallspace
\ppart \pts{2} Generalize (in your own words or in symbols) 
to give the elements of $S_n$. 
\smallspace
\solution{
  $S_n$ contains $2^n+1$ elements (including 0 and 1) evenly spaced
  along the unit interval; i.e., $S_n=\set{i/2^n|0\leq i\leq 2^n}$.  }

\ppart \pts{7} Prove by induction that for all $n \in\nats$,
$1/3\not\in S_n$.  You will probably want to strengthen the induction
hypothesis.  You may not assume your generalization from the previous
part is true; you must prove that statement if you wish to use it.

\solution{Strengthen the theorem to
\[ P(n)=\mathrm{``For\ all\ }a/b\in S_n\mathrm{\ with\ }a,b\in\naturals\mathrm{\ where\ }a/b\mathrm{\ is\ in\ reduced\ form,\ }b=2^k\mathrm{\ for\ some\ }k\mathrm{"} \]
Clearly, if $\forall n\ P(n)$, then $\forall n\ 1/3\not\in S_n$.
Thus, we need only prove $\forall n\ P(n)$.

\textit{Base cases.} $0=0/2^0$, $1=1/2^0$.

\textit{Induction.} Assume $P(n)$.  By the construction of $S_{n+1}$,
all elements of $S_{n+1}$ are of the form $(x+y)/2$ for some $x,y\in
S_n$.  Fix any two such elements $x,y\in S_n$, where (by the induction
hypothesis) $x=a/2^k$ and $y=c/2^\ell$ with $a,b,k,\ell\in\naturals$.

Assume WLOG $k\geq\ell$.  Then,
%
\begin{eqnarray*}
(x+y)/2
& = & (a/2^k + c/2^\ell)/2 \\
& = & (a/2^k + c2^{k-\ell}/2^k)/2 \\
& = & (a + c2^{k-\ell})/2^{k+1}
\end{eqnarray*}
%
While this may not be in reduced form, reduction cannot introduce any
non-2 factors into the denominator, so this fits the form specified by
the theorem.  Therefore, $P(n+1)$.

By induction, $\forall n\ P(n)$.  Thus, $\forall n\ 1/3\not\in
S_n$.\kpfend

}

\eparts

\nextproblem
\problem\pts{10}  \textbf{Precedence Relations}

Death is planning the end of the world.  This involves a number of
tasks each of which takes one minute to complete.  The prerequisites
associated with these tasks are listed below.
\begin{center}
\begin{tabular}{cll}
\textsc{Abbrv.} & \textsc{Task} & \textsc{Prerequisites} \\
C & Compose a requiem & \\
N & Notify the UN & B \\
D & Signal the daemons & B \\
B & Blow the trumpet & \\
T & Sell T-shirts: ``All I got was this lousy t-shirt.'' &
N \\
Q & Grade the 6.042 quiz & S \\
G & Open the gates & D,N \\
S & Put out the sun & C,N 
\end{tabular}
\end{center}

\begin{problemparts}

  \ppart\pts{5} Represent the tasks and their prerequisites as a
  directed graph.  
  
  \bigskip

  \solution{
  \centerline{\psfig{figure=/a/class/6.042/fall00/handouts/figures/death.eps,height=2.5in}}

  \bigskip
  }

  \ppart\pts{5} Death is omnipotent and can therefore work on as many
  tasks at a time as he wishes.  What is the minimum amount of time
  required for him to end the world?  Why?  (An explanation without
  proof is fine.)

 \bigskip

 \solution{
 The minimum required time is 4 (length of the critical path B-N-S-Q).
 }
 \smallspace
\end{problemparts}

\nextproblem 
\problem\pts{10} \textbf{Graphs} 

The vertices of a directed graph can be
partitioned into {\em strongly-connected components}.  Two vertices
$u$ and $v$ belong to the same strongly connected component if there
is a path from $u$ to $v$ and a path from $v$ to $u$.  A strongly
connected component may consist of a single vertex.

Math Moose has noticed a strange phenomenon.  He starts with a
directed graph and partitions the vertices into strongly-connected
components.  He then removes all edges that connect two vertices in
the same strongly-connected component.  The resulting graph always
seems to be acyclic.

An example is worked out in the figure below.  The original directed
graph is shown on the left.  The vertices $a$, $b$, and $c$ form one
strongly-connected component.  The single vertex $d$ forms a second
strongly-connected component.  Math Moose removes the edges $a
\rightarrow b$, $b \rightarrow c$, and $c \rightarrow a$, since these
edges connect vertices in the same strongly-connected component.  The
resulting graph is shown on the right.  Note that this graph is
acyclic.

\bigskip

\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/figures/scc.eps,height=1.5in}}

\bigskip

Use proof by contradiction to show that for every directed graph,
application of Math Moose's procedure gives a directed acyclic graph.

\solution{
\begin{proof}
Let $G = (V,E)$ be an arbitrary directed graph.  Let $G' = (V,E')$ be
the directed graph that remains after we remove all edges that connect
two vertices in the same strongly-connected component.

The proof is by contradiction.  Suppose that $G'$ is not acyclic.
Then it must have a cycle.
Then let $u$ and $v$ be consecutive nodes in a directed cycle.  There
is a path from $u$ to $v$ consisting of a single edge.  There also is
a path from $v$ to $u$, because the nodes are in a cycle.  Since every
edge in $G'$ is also in $G$, these same two paths exist in the
original graph $G$.  Therefore, $u$ and $v$ are in the same
strongly-connected component of $G$.  But then the edges on the path
from $u$ to 
$v$ should have been removed during the construction of $G'$.  Since
these edges were not removed, we have a contradiction.  Therefore,
$G'$ is acyclic. 
\end{proof}
}

\nextproblem
\problem\pts{5}  \textbf{Graphs} 

Let $G = (V,E)$ be a simple, undirected graph, and let $C$ be a set of
colors.  Define a \textit{partial coloring of} $G$ \textit{using} $C$
to be a function that assigns to each node in $V$ either a color in
$C$ or no color.  (That is, it colors some, none, or all of the nodes
using colors in $C$.)  Define a \textit{partly colored graph} to be a
simple, undirected graph $G = (V,E)$ together with a partial coloring
of $G$.

Prove the following fact about partly colored graphs:
\begin{center} 
\begin{minipage}{6in} 
  In a partly colored graph, any walk connecting a colored node to an
  uncolored node must include a colored node adjacent to an uncolored
  node.
\end{minipage} 
\end{center} 
 
\solution{
\begin{proof}
Consider the path $p=v_1v_2\cdots v_k$, of which $v_1$ is 
  colored and $v_k$ is uncolored.  Assume there is no edge 
  $(v_i,v_{i+1})$ such that $v_i$ is colored and $v_{i+1}$ is 
  uncolored.  Then, by induction starting from $v_1$, $v_i$ are 
  colored for all $i$, so $v_k$ is colored; this is a contradiction. 
\end{proof}
} 
 
 
\nextproblem 
\problem\pts{15}  \textbf{Algorithms} 

Let $G = (V,E)$ be a simple, undirected graph.  The following
algorithm, $RedBlue$, manipulates partial colorings of $G$ using $C =
\set{\mathrm{red,blue}}$.  (Partial colorings are defined in the
previous problem.)

\begin{center} 
\begin{minipage}{5in} 
  Initially, one vertex $r$ of $G$ is colored red, and all the other
  vertices are uncolored.  At each step, one of two events occurs:
  \begin{enumerate} 
  \item Some uncolored vertex $v$ that is adjacent to a red 
    vertex becomes blue. 
  \item Some uncolored vertex $v$ that is adjacent to a blue 
    vertex becomes red. 
  \end{enumerate} 
  If neither rule can be applied, the algorithm terminates. 
\end{minipage} 
\end{center} 
 
\bparts 
 
\ppart\pts{3} Formalize this algorithm as a state machine; that is, define 
$Q$, $Q_0$, and $\delta$. 
 
\smallspace
\solution{A state $q$ consists of a (total) function $f$ from $V$ to 
  $\{ red, blue, uncolored \}$. 
  A start state is any state in which $f$ maps exactly one $v \in V$
  to red, and all others to uncolored. 
  The transitions are all of the form: 
  \begin{eqnarray*} 
    (q,q')\in\delta & \iff & \exists v \in V\ q.f(v)=\mathrm{uncolored} \\ 
      && \wedge \big[\left(q'.f(v)=\mathrm{red}\wedge\exists w\
  f(w)=\mathrm{blue}\wedge (v,w)\in E\right) \\ 
      && \ \ \ \vee \left(q'.f(v)=\mathrm{blue}\wedge\exists w\
  q.f(w)=\mathrm{red}\wedge (v,w)\in E\right)\big] \\ 
      && \wedge \forall w \neq v \ q.f(w) =q'.f(w) 
    \end{eqnarray*} 
 
} 

\newpage
 
\ppart\pts{3} Prove that the algorithm eventually terminates.   
 
\smallspace
\solution{We describe a termination function. 
  Define the value of the termination function to be the number $d$ of
  uncolored vertices.  Each step decreases $d$, so we can appeal to
  the Termination Theorem and conclude that the algorithm always
  terminates.
  Alternatively, we can expand the proof a bit more: since $d$ starts at 
  $n-1$ and is always $\geq 0$, it must eventually reach some minimum 
  value (by well-ordering), whereupon the algorithm terminates.} 
 
 
\ppart\pts{3} %
Using the fact stated in Problem 6, prove that if $G$ is connected,
then all vertices are colored when the algorithm terminates.
 
\smallspace
\solution{Say the algorithm terminates with some vertex uncolored. 
Since the graph is connected, there is a path from $v$ to some colored 
vertex $w$.  By the given fact, there must be an edge along this path 
for which one endpoint $x$ is colored and the other $y$ is uncolored. 
We can apply one of the two steps above, assigning to $y$ the opposite 
of $x$'s color.  Thus, the algorithm should not have terminated yet.} 

\newpage  
\ppart\pts{3} %
Consider applying this algorithm to \textit{bipartite} graphs, i.e.,
graphs in which the vertices can be partitioned into two sets $A$ and
$B$ such that there is no edge between any pair of vertices in $A$,
and similarly for $B$.  Suppose the node $r$ that is colored red in
the initial state is in set $A$.  Using the Invariant Theorem, prove
that in any reachable state, only vertices of $A$ are colored red and
only vertices of $B$ are colored blue.
 
\smallspace 
\solution{ 
The Invariant Theorem requires that we show that the condition is true
in all the start states, and that it is preserved by every step.


  We need to show that the invariant is preserved from one step to the 
  next, which we do by induction on the number of colored vertices. 
   
  $P(n)=$``After $n$ vertices are colored, all red vertices are in $A$ 
  and all blue vertices are in $B$.'' 
   
  \textit{Base case.} In any start state, there is exactly one red 
  vertex in $R$---by construction---and no blue vertices.  Therefore, 
  $P(1)$. 
   
  \textit{Induction.} Assume $P(n)$.  Then, consider an execution in 
  which $n+1$ vertices are colored.  Consider the vertex $i$ which was 
  colored last.  If we uncolor it, we can apply the induction 
  hypothesis and conclude that all red vertices were in $R$ and all 
  blue vertices were in $B$. 
   
  Now we must prove that vertex $i$ is colored correctly.  Assume WLOG 
  that vertex $i$ is in $B$.  For $i$ to have been colored, it must 
  have been the case that $i$ was adjacent to a colored vertex; but 
  all vertices adjacent to $i$ are in $R$ (by the definition of 
  bipartite), so $i$ must have been colored blue.  This satisfies the 
  invariant theorem, so $P(n+1)$. 
   
  Thus, $\forall n\ P(n)$, so all red vertices are in $R$ and all blue 
  vertices are in $B$.  
} 
 
\ppart\pts{3} Combine the previous parts to prove that when run on a 
 connected bipartite graph, the above algorithm terminates and outputs 
 a valid 2-coloring. 
 
\smallspace 
\solution{We proved the algorithm terminates on connected graphs with 
all vertices colored.  By the invariant above, this means all vertices 
in $R$ are red and all vertices in $B$ are blue.  By the definition of 
bipartite, there exists no pair of like-colored vertices connected by 
an edge, so this is a valid 2-coloring.  } 
 
\eparts 

\end{problems}

\end{document}
