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

\newif\ifspaceout
\spaceoutfalse
\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)}

\renewcommand{\solution}[1]{\par\textbf{Solution.} #1}

\newcommand{\coverpage}[1]{\ifshowsolutions \else #1 \fi}

\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}
%\querysol{q1}{Quiz 1}{Match 8 2000}{q1sol}{Quiz 1 Solutions}{Match 15 2000}

\ifshowsolutions
\qsol{1}{March 15 2000}
\else
\exam{ Quiz 1}{March 8 2000}
\fi

%\titlebar

\coverpage{
\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{c@{\hskip 3em}c@{\hskip 3em}c@{\hskip 3em}c}
Carl & David & Josh & Ken \\
\ &&& \\
Kyle & Robert & Shishir & Victor
\end{tabular}
\end{center}

\medskip

\noindent Write the hour at which your Friday recitation begins \brule{3em}

\medskip

\begin{closeitemize}
\item This quiz is open book/notes.  

\item There are 11 pages with 7 problems totaling 70 points.  Problem 
  parts are labeled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these
    pages may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

\item You may assume any of the results presented in class or in the
  lecture notes.

\item Show your work, as partial credit will be given.  You will be
  graded not only on the correctness of your answer, but also on the
  clarity with which you express it.  {\bf Be neat and write legibly}.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\medskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  10 & & \\ & & & \\\hline & & &\\
2 &  10 & & \\ & & & \\\hline & & &\\
3 &  10 & & \\ & & & \\\hline & & &\\
4 &  10 & & \\ & & & \\\hline & & &\\
5 &  10 & & \\ & & & \\\hline & & &\\
6 &  5 & & \\ & & & \\\hline & & &\\
7 &  15 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 70 & & \\
& & &\\
\hline
\end{tabular}
\end{center}


\newpage
}

\begin{problems}

\problem\pts{10} \textbf{Quantifiers}

Consider the following predicates where the universe of discourse is
the set of all people:
\begin{description}
\item[$P(x)$:] $x$ is a hacker
\item[$Q(x)$:] $x$ is an MIT student
\item[$R(x)$:] $x$ is an artist
\item[$S(x)$:] $x$ is willing to waltz
\end{description}
Express each of the following statements using quantifiers, logical
connectives, and and the above predicates:
\begin{problemparts}
\ppart  \onept No hackers are willing to waltz.
\smallspace\solution{$\not\exists x\ \ P(x)\wedge S(x)$}
\ppart  \onept No artists are unwilling to waltz.
\smallspace\solution{$\not\exists x\ \ R(x)\wedge \neg S(x)$}
\ppart  \onept All MIT students are hackers.
\smallspace\solution{$\forall x\ \ Q(x)\Rightarrow P(x)$}
\ppart  \onept MIT students are not artists.
\smallspace\solution{$\forall x\ \ Q(x)\Rightarrow \neg R(x)$}
\ppart  \pts{4} Does (d) follow logically from (a), (b), and (c)?  If so, give
a proof.  If not, give a counterexample.
\smallspace
\solution{Assume (a), (b), and (c).  Then, we want to prove that, for
any $x$ such that $Q(x)$ (for any MIT student), it follows that $\neg
R(x)$ (that student is not an artist).

From (c), we know that $P(x)$ (that the student is a hacker).
If we rearrange (a) to \[\forall x\ \ P(x)\Rightarrow \neg S(x)\]
then clearly $\neg S(x)$ (the student is not willing to waltz).  So,
if we rearrange (b) to \[\forall x\ \ \neg S(x)\Rightarrow \neg R(x)\]
it follows that $\neg R(x)$ (the student is not an artist).
}
\ppart  \onept Translate into English:
$(\forall x) (R(x) \vee S(x) \implies Q(x))$.
\smallspace\solution{All who are artists or people willing to waltz
are MIT students.}
\ppart   \onept Translate into English: $(\exists x) (R(x) \wedge
\neg Q(x)) \implies (\forall x)(P(x) \implies S(x))$.
\smallspace\solution{If there is an artist who is not an MIT student,
then all hackers are willing to waltz.}
\end{problemparts}

\nextproblem

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

Prove {\bf by induction} (other methods will not receive credit) that
\[
(1\cdot 2) + (2 \cdot 3) + (3 \cdot 4) + \cdots + (n-1)n = 
\frac13 (n-1)\cdot n\cdot (n+1)
\]
whenever $n$ is a natural number greater than 1.

\solution{
Prove $P(n)::=\ (1\cdot 2) + (2 \cdot 3) + (3 \cdot 4) + \cdots +
(n-1)n = \frac{1}{3}(n-1)\cdot n\cdot (n+1)$

\textbf{Basis.} ($P(2)$) $(1\cdot 2) = \frac{1}{3}(1)\cdot 2\cdot
(3)$.

\textbf{Induction.}
Assume $P(n)$.  Prove $P(n+1)$.
\begin{eqnarray*}
\underbrace{(1\cdot 2) + (2 \cdot 3) + (3 \cdot 4) + \cdots +
(n-1)n}_{\mathrm{Apply\ IH}} + n(n+1) &=& \frac{1}{3}(n-1)\cdot n\cdot
(n+1) + n(n+1) \\
&=&n(n+1)\left[\frac{1}{3}(n-1) + 1\right] \\
&=&n(n+1)\left[\frac{1}{3}n+\frac{2}{3}\right] \\
&=&\frac{1}{3}n(n+1)\left[n+2\right]
\end{eqnarray*}
}

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

The denizens of the land of Frohike worship prime numbers:
their currency---the Eebae$^{\textrm{\tiny TM}}$---only uses coins of
values 5, 7, and 11 Eebaes.

The Frohikies have discovered over time that any value of at least 14
Eebaes can be produced using some combination of these coins, but some
values below 14 are not possible.

Prove by induction that all values of at least 14 Eebaes can be made
from these three coin values.

\solution{We wish to prove $P(n)=$``$n=5a+7b+11c$, for some
  $a,b,c\in\naturals$'' for all $n\geq 14$.

  \textit{Base cases.}

  $P(14)=7*2$

  $P(15)=5*3$

  $P(16)=5*1+11*1$

  $P(17)=5*2+7*1$
  
  $P(18)=7*1+11*1$
  
  \textit{Induction.} Fix $N\geq 19$.  Assume $P(n)$ for all $14\leq n\leq
  N$.  Prove $P(N+1)$.
  
  Any number $N+1\geq 19$ can be made by adding $5$ to $N+1-5=N-4$.
  Since we have assumed $P(N-4)$ (by our induction hypothesis),
  $P(N-4)\Rightarrow P(N+1)$.

  By strong induction, $\forall n\geq 14:\ P(n)$.\kpfend
}
\fi

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

\begin{problemparts}

  \ppart\onept What is the common name for the reflexive closure of the
  ``less than'' relation?
\smallspace
\solution{less than or equal to}

  \ppart\onept What is the common name for the transitive closure of the
  ``child of'' relation?
\smallspace
\solution{descendant of}

\ppart\pts{2} What is the common name for the inverse of the ``teaches''
relation (that is, if $xTy$ means $x$ teaches $y$, how do we say
$aT^{-1}b$)? 
\smallspace
\solution{is taught by}

  \ppart\pts{3} Consider the partial order ``$aRb$ iff $a$ divides $b$ without
  remainder'' on the universe of natural numbers {\bf greater than 1}.
  What are the minimal elements under this relation usually called?
\smallspace
\solution{primes}

  \ppart\pts{3} Is the relation ``$xRy$ iff $x=y$ or $x$ is {\bf not} $y$'s
  roommate'' an equivalence relation?  Why or why not?
\end{problemparts}
\solution{No, because it is not transitive.  If $x$ and $y$ are
roommates but neither is a roommate of $z$, then $xRz$ and $zRy$ but
$\neg xRy$.}

\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.  
  
  \smallspace
  \solution{This is very similar to the constructions in the notes.}


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

  \solution{4 time units, since that is the length of the critical
path.}

\end{problemparts}




\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{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. 
  } 
 
 
\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$. 
 
\largespace
\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*} 
 
} 
 
\ppart\pts{3} Prove that the algorithm eventually terminates.   
 
\mediumspace
\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.
 
\largespace
\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.} 
 
\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.
 
\largespace 
\solution{ 
The Invariant Theorem requires that we show some 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}
% LocalWords:  pt bij inj sur FBT fbt Shishir Frohike Eebae Eebaes Frohikies
% LocalWords:  iff Abbrv uncolor
