\documentclass[12pt]{article}
\input{macros-course}

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

%% Quiz 2

\ifshowsolutions
  \qsol{2}{October 19, 2001}{\stamp}
\else
  \quiz{2}{October 19, 2001}{\stamp}

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

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{l@{\hskip 3em}l@{\hskip 3em}l@{\hskip 3em}l}
Yu-Han & Christos & Nikos & Ashish \\
\ &&& \\
Thien-Loc & Jaime & Tina & Tong
\end{tabular}
\end{center}

%\noindent Write the hour at which your Thursday tutorial begins \brule{3em}.

\medskip

\begin{closeitemize}
\item This quiz is \textbf{closed book}.  There is an Appendix that
includes some standard definitions.  The first occurrence of an item
defined in the appendix appears in \textbf{boldface}.

\item There are four (4) problems totaling 100 points.  Problems 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 \remove{Show your work, as partial credit will be given.}
\textbf{Be neat and write legibly}.  You will be graded not only on the
correctness of your answer, but also on how clearly you present it.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\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 &  15 & & \\ & & & \\\hline & & &\\
2 &  25 & & \\ & & & \\\hline & & &\\
3 &  30 & & \\ & & & \\\hline & & &\\
4 &  30 & & \\ & & &\\
\hline
\hline
& & &\\
Total & 100 & & \\
& & &\\
\hline
\end{tabular}
\end{center}

\newpage
\fi

\begin{problems}

\problem\pts{15}  % Fall 2000, practice quiz, revised to be in better taste

Students are planning a campaign against MIT's requirement that they join
the meal plan.  This involves a number of tasks, each of which takes one
day to complete.  Some tasks cannot be started until other prerequisite
tasks are complete.  The tasks and their prerequisites are listed below.

\begin{center}
\begin{tabular}{cll}
\textsc{Abbrv.} & \textsc{Task} & \textsc{Prerequisites} \\
C & Cook for themselves & \\
N & Notify Chuck & B \\
D & Signal the Free Food Daemons & B \\
B & Blow the trumpet & \\
T & Sell T-shirts: ``Where do you want to eat today?'' &
N \\
Q & Take the 6.042 quiz & S \\
G & Go to Campus Dining Review meeting & D,N \\
S & Suppress Aramark and condescending admins & C,N 
\end{tabular}
\end{center}

\begin{problemparts}

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

\solnospace{
\centerline{\includegraphics[height=2.5in]{figures/death}}
%\centerline{\psfig{figure=/a/class/6.042/fall00/handouts/figures/death.eps,height=2.5in}}
}

\ifshowsolutions
{}
\else
\vspace{2.5in}
\fi


\ppart\pts{8} So many MIT students are unhappy with the meal plan that
finding students to work on several tasks at once is no problem.  For
example, if there were no prerequisites, students could do all the tasks
in parallel, and the campaign could be completed in one day --- even
though it would not be a good idea to blow the trumpet during the 6.042
Quiz \texttt{:-)}

In this situation, what is the minimum number of days needed to complete
the campaign against the meal plan?  Briefly explain why.

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

\ifshowsolutions
{}
\else
\vspace{1.5in}
\fi



\end{problemparts}


\ifshowsolutions
{}
\else
\newpage
\fi

%%--------------------------------------------------------
%% source:  new, similar to tutorial problem

\problem\pts{25} Four VI-A students would like a position at a company.
There are four companies, each with one position for a VI-A student.  The
students give the VI-A office their resum\'es and order of preference for
the companies.  The VI-A office sends the resum\'es to the companies and
the companies report back their ranking of the students.  Below are the
students' rankings of the companies and the companies' rankings of the
students.

\begin{center}
\begin{tabular}{l|c} 
Student & Ranking of Companies \\ \hline
Nikos   & Lotus, IBM, Compaq, Akamai \\
Yu-Han  & Compaq, Lotus, Akamai, IBM \\
Radhika & Compaq, Lotus, IBM, Akamai\\
Tina    & Akamai, Compaq, Lotus, IBM 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{l|c}
Company & Ranking of Students \\ \hline
Compaq  & Yu-Han, Tina, Nikos, Radhika \\
Lotus   & Yu-Han, Radhika, Nikos, Tina \\
IBM     & Radhika, Yu-Han, Nikos, Tina \\
Akamai  & Tina, Yu-Han, Radhika, Nikos
\end{tabular}
\end{center}

\bparts

\ppart\pts{10} Based on the rankings, the VI-A office will assign one
student to each company so the assignment forms a stable marriage set.
Exhibit a stable marriage set for this problem.

\solnospace{Running the Mating Algorithm, where students are boys and
companies are girls, the result is the following assignment:
\begin{center}
\begin{tabular}{l|l|} 
Student & Companies \\ \hline
Nikos  & IBM \\
Yu-Han     & Compaq \\
Radhika   & Lotus\\
Tina    & Akamai
\end{tabular}
\end{center}
}

\ifshowsolutions
{}
\else
\newpage
\fi

\ppart\pts{7} Briefly suggest why students and companies would both want
the VI-A office's assignment to be stable.

\solnospace{If an assignment was not stable, it would have a rogue pair: a
student and company who preferred each other over the company and student
they got assigned to.  So they would both be better off together and they
would have an incentive to disrupt the VI-A office's assignment, leaving
everyone uncertain about what/who their final assignment will be.}

\ifshowsolutions
{}
\else
\vspace{3.5in}
\fi

\ppart\pts{8} An unstable assignment is, by definition, one that has a
\emph{rogue pair}.  In this case there is VI-A student, $S$, and a
company, $C$, such that $(S,C)$ would be a rogue pair in \emph{any}
assignment in which $S$ was not assigned to $C$.  Give an example of such
a pair $(S,C)$, and briefly explain why your example has this property.

\solnospace{Tina likes Akamai best and Akamai likes Tina best.  So these
two would be sure to prefer each other over their spouses if they were not
married, \ie they would be a rogue pair if they were not married.  Yu-Han
and Compaq are another such pair.}

\ifshowsolutions
{}
\else
\newpage
\fi

\iffalse \ppart\pts{7} It happens in this case that the student-pessimal
assignment is the same as the student-optimal one.  Explain why this
implies that there is only one possible stable assignment.

\solnospace{In the student-optimal (pessimal) assignment, a student $S$,
is assigned to their most (least) preferred company, $C$, among all
possible companies they could be assigned to in a stable assignment.  So
in any stable assignment, $S$ would be to be assigned to a company they
like no worse than $C$ nor more than $C$, so they have to be assigned to
$C$ no matter what.}

\ifshowsolutions
{}
\else
\vspace{3in}
\fi

\ppart\pts{5} What is a simple way to verify that the student-optimal and
student-pessimal stable marriage sets are the same?

\solnospace{We know the student-pessimal assignment is the
company-optimal one, so just run the Mating Algorithm treating students
are girls and companies as boys, and check you get the assignment as in
part (a).}
\fi

\eparts


\ifshowsolutions
{}
\else
\newpage
\fi


%%--------------------------------------------------------
%% source: Fall99 Q2, prob 4
%% topics: {Graphs, Trees, State Machines, Counting, Well-order}

\problem\pts{30}
We apply the following operation to a \textbf{simple graph} $G$:
pick two vertices $u \neq v$ such that either
\begin{enumerate}
\item there is an edge of $G$ between $u$ and $v$ and there is also a path
from $u$ to $v$ which does \emph{not} include this edge; in this case,
delete the edge $\set{u,v}$.

\item there is no path from $u$ to $v$; in this case, add the edge
$\set{u,v}$.
\end{enumerate}

Keep repeating these operations until it is no longer possible to find two
vertices $u \neq v$ to which an operation applies.

Assume the vertices of $G$ are the integers $1,2,\dots,n$ for some $n \geq
2$.  This procedure can be modelled as a state machine whose states are
all possible simple graphs with vertices $1,2,\dots,n$.  $G$ is the start
state, and the final states are the graphs on which no operation is
possible.

\bparts

\ppart\pts{4} Let $G$ be the graph with vertices $\set{1,2,3,4}$ and edges
\[
\set{\set{1,2},\set{3,4}}
\]
How many possible final states are reachable from start state
$G$? \hfill \brule{1in}

\solnospace{It's not possible to delete any edge.  The procedure can only
add an edge connecting exactly one of vertices 1 or 2 to exactly one of
vertices 3 or 4, and then terminate.  So there are four possible final
states}

\ppart\pts{8} \label{derived} On the line next to each of the derived
state variables below, indicate the \emph{strongest} property from the
list below that the variable is guaranteed to satisfy, no matter what the
starting graph $G$ is.  The properties are:
\begin{center}
\begin{tabular}{cccccc}
\emph{constant} & \emph{increasing} & \emph{decreasing} &
\emph{nonincreasing} & \emph{nondecreasing} & \emph{none of these}
\end{tabular}
\end{center}

For any state, let $e$ be the number of edges in it, and let $c$ be the
number of \textbf{connected components} it has.  Since $e$ may increase or
decrease in a transition, it does not have any of the first four
properties.  The derived variables are:
\begin{enumerate}

\item[0)] $e$ \hfill \underline{\emph{none of these}}


\item[i)] $c$ \hfill \brule{1.0in}

\solnospace{nonincreasing}

\item[ii)]  $c+e$ \hfill \brule{1.0in}

\solnospace{nonincreasing}

\item[iii)] $2c+e$ \hfill \brule{1.0in}

\solnospace{decreasing}

\item[iv)] $(c,e)$, under the \textbf{lexicographic order} on $\nats \cross \nats$.
\hfill \brule{1.0in}

\solnospace{decreasing}

\end{enumerate}

\ifshowsolutions
{}
\else
\newpage
\fi

\ppart\pts{8} Explain why, starting from any state, $G$, the procedure
terminates.  If your explanation depends on answers you gave to part~(b),
you must justify those answers.

\solnospace{4 pts: The derived variable iii) is a natural-number valued
variable and is decreasing.  \emph{Alternative answer}: derived variable
iv) is decreasing under the lexicographic order on $\nat \cross \nats$
which we know from Problem Set 6 is a well-ordered set.

We saw in Notes \#6 that this means the procedure must terminate.

4pts: To show that the variable iii) decreases, note that the rule for
deleting an edge ensures that the connectedness relation does not change,
so neither does the number of connected components; therefore the variable
decreases by one when an edge is deleted.  The rule for adding an edge
ensures that the number of connected components decreases by one, so the
variable changes by $-2$ for the reduced number of components and $+1$ for
the added edge, for a net decrease of 1.  This also shows that variable
iv) decreases.}

\ifshowsolutions
{}
\else
\vspace{3in}
\fi

\ppart\pts{10} Prove that any final state must be an \textbf{unordered
tree} on the set of vertices, \ie a spanning tree.

\solnospace{We use the characterization of a tree as a cycle-free,
connected, simple graph.

A final state must be connected, because otherwise there would be two
vertices with no path between them, and then a transition adding the edge
between them would be possible, contradicting finality of the state.

A final state can't have a cycle, because deleting any edge on the
cycle would be a possible transition.}

\eparts

\ifshowsolutions
{}
\else
\newpage
\fi

%%-----------------------------------------------------------
%% source: Fall 99 final exam
%% topic: Trees and Structural Induction

\problem\pts{30} A \emph{full binary tree} with its {\it vertices} and
{\it leaves} is defined as follows:

\begin{itemize}

\item A simple graph with one vertex is a full binary tree.  The vertex is
called the \emph{root} of the tree.  In this case, the \emph{set of
leaves} of the tree is the set whose sole member is the root, and the
\emph{set of vertices} is the same as the set of leaves.

\item If $B_1$ and $B_2$ are full binary trees such that the sets of
vertices of $B_1$ and $B_2$ are disjoint, then a simple graph consisting
of a new vertex with edges from the new vertex to the roots of $B_1$ and
$B_2$ is also a full binary tree, $B$.  The \emph{root of $B$} is the new
vertex.  The set of \emph{vertices of $B$} is the union of the set of
vertices of $B_1$ and the set of vertices of $B_2$ along with the new
vertex.  The set of \emph{leaves of $B$} is the union of the set of leaves
of $B_1$ and the set of leaves of $B_2$.

\end{itemize}

For example, two full binary trees are shown in the following Figure.
\ifshowsolutions
{}
\else
\begin{figure}[htb]
\begin{center}
\includegraphics[width=4.5in,height=3.5in]{figures/q2-trees}
\end{center}
\caption{Full binary trees}
\label{fig:trees}
\end{figure}
\fi

You will be asked to prove by structural induction that for all full
binary trees, $B$,
\begin{equation}\label{lv}
\card{\text{leaves}(B)} = \frac{\card{\text{vertices}(B)}+1}{2}.
\end{equation}
Let the induction hypothesis, $P(B)$, be equation~(\ref{lv}).

\bparts

\ppart\pts{7} Prove the base case(s) of your induction hypothesis.

\solnospace{
\textbf{Base case} $P(\text{single root})$: there is 1 leaf, 1 vertex and
indeed $1=(1+1)/2$.}

\ifshowsolutions
{}
\else
\vspace{2.0in}
\fi


\ppart\pts{8} Carefully state what must be proved in the induction step.

\solnospace{ \textbf{Induction step}: Prove $P(B)$, given that $B$ has a
root $r$ connected to two full binary trees $B_1$, $B_2$ such that that
$P(B_1)$ and $P(B_2)$ are true.  That is, prove that equation~(\ref{lv})
holds assuming that it holds when $B_1$ is substituted for $B$ and when
$B_2$ is substituted for $B$.}

\ifshowsolutions
{}
\else
\newpage
\fi

\ppart\pts{15} Complete the proof of the induction step.

\solnospace{
\begin{eqnarray*}
\card{\text{leaves}(B)} & = & \card{\text{leaves}(B_1) \union \text{leaves}(B_2)}\\
 & = & \card{\text{leaves}(B_1)} + \card{\text{leaves}(B_2)} \qquad \text{because
       vertices of $B_1$ and $B_2$ are disjoint}\\
 & = & \frac{\card{\text{vertices}(B_1)}+1}{2} +
       \frac{\card{\text{vertices}(B_2)}+1}{2} \qquad\text{by induction hypothesis}\\
 &= & \frac{(1+ \card{\text{vertices}(B_1)}+
                \card{\text{vertices}(B_2)}) + 1}{2}\\
 & = & \frac{\card{ \set{r} \union \text{vertices}(B_1) \union
             \text{vertices}(B_2)} + 1}{2} \qquad \text{disjointness again}\\
 & = & \frac{\card{\text{vertices}(B)} + 1}{2}
\end{eqnarray*}

We took off one point for not mentioning disjointness.  Five students got
99 instead of a perfect 100 on the quiz because of this quibble.}

\eparts

\end{problems}


\ifshowsolutions
{}
\else
\newpage
\fi

\section*{Appendix}
\begin{itemize}

\item A \emph{simple graph} is an undirected graph with at most one edge
between each pair of vertices.

\item A \emph{simple path} in a simple graph is a sequence of one or more
\emph{distinct} vertices $v_1,\dots,v_k$ such that there is an edge
between $v_i$ and $v_{i+1}$ for $1 \le i < k$.

\item A \emph{simple cycle} in a simple graph is a simple path
$v_1,\dots,v_k$ such that $k > 2$ and there is an edge between $v_k$ and
$v_1$.

\item A \emph{connected component} of a simple graph is a set, $C$, of
vertices such that
   \begin{itemize}
   \item every pair of vertices in $C$ is connected by a path, and
   \item every vertex connected to a vertex in $C$ is also in $C$.
   \end{itemize}

\item The \emph{lexicographic order}, $\prec$, on $\nats \cross
\nats$ is defined by the rule:
\[
(c_1, e_1) \prec (c_2, e_2) \ \iff \ [c_1 < c_2 \lor (c_1 = c_2 \land
e_1 < e_2)]
\]

\item An \emph{unordered tree} is a connected simple graph with no simple
cycles.

\iffalse

\item the \emph{powerset}, $\power(S)$, of a set, $S$, is $\set{A
\suchthat A \subseteq S}$.

\item the \emph{divides} relation: $n \divides m \iff \exists k \in
\nats\; kn = m$.

\item A \emph{maximal} (\emph{minimal}) element in a poset $(A, \le)$, is
an element of $A$ that is not strictly smaller (larger) than any other
element of $A$.
\fi

\end{itemize}

\end{document}                            
