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

%\backwardscompatibility	% !! use for backwards compatibility
%\showsolutions	 		% !! use to force solutions & skip query
%\hidesolutions			% !! use to force no solutions & skip query


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

\instatements{
\renewcommand{\exampreamble}{	% !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llllll}
Ching & Edmond & Karen & Kilian & Mana & Min
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This quiz is \textbf{closed book}, but there is an \textbf{appendix}
  with standard definitions.
  \item 
  There are five problems totaling 100 points. Total time is 80 minutes. 
  %% 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
  assigned reading.
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
  \item 
  GOOD LUCK!
  \end{itemize}}}

\begin{document} 
\quiz{1}			% !! start the paper

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

\instatements{\newpage}

\begin{examproblem}{22}
Let $G$ be a directed graph.  Let $P(x, y)$ mean that there is a path
from vertex $x$ to vertex $y$ that contains at least one edge.
Express each of the following sentences in terms of $P$, quantifiers,
logical connectives, and other mathematical symbols, where the domain
of discourse is the set of vertices of $G$.

\bparts

\ppart[4] There is a path from vertex $x$ to every other vertex in $G$.

\solution[\vspace{0.75in}]{\[
\forall y\ (y \neq x \implies P(x,y))
\]}

\ppart[4] There is a cycle containing the vertex $x$.
\solution[\vspace{0.75in}]{\[
P(x,x)
\]}

\ppart[4] $G$ is a directed acyclic graph.
\solution[\vspace{0.75in}]{
\[
\forall x\ \neg P(x,x)
\]
}

\eparts

A nonempty subset $C$ of the vertices of $G$ is \emph{strongly
connected} if there is a path from $u$ to $v$ for every pair of
distinct vertices $u, v \in C$.  (Note that a subset $C$ consisting of
a single vertex is strongly connected by default.)  A \emph{strongly
connected component} of $G$ is a strongly connected set of vertices
$C$ such that no strict superset of $C$ is also strongly connected.
Express each of the following sentences in logic notation as before.

\bparts

\ppart[4] Vertices $x$ and $y$ belong to the same strongly connected
component.

\solution[\vspace{0.75in}]{
\[
x=y \lor (P(x,y) \land P(y,x))
\]}

\ppart[6] The graph $G$ has exactly two strongly connected components.

\solution[\vspace{0.75in}]{The solution below is accompanied by text
on the right to make it more understandable.

\[
\begin{array}{lll}
\exists x\ \exists y\ & & \text{There exist vertices $x$ and $y$} \\
& \neg(x=y \lor (P(x,y) \land P(y,x))) & \text{which are not in the same component} \\
& \land\ \forall z\ & \text{such that every vertex $z$} \\
& (z=y \lor (P(z,y) \land P(y,z)))\ \lor &
	\text{is in the same component as $y$ or} \\
& (x=z \lor (P(x,z) \land P(z,x))) & \text{in the same component as $x$.}
\end{array}
\]
}

\eparts

\iffalse
\instatements{\newpage}

Let $R$ be a binary relation on the set of strongly connected
components of a graph $G$.  The relation $C_1\,R\,C_2$ holds iff there
is a path from some vertex in $C_1$ to some vertex in $C_2$.  Next to
each proposition below, circle \textbf{true} if the statement is true
for all graphs $G$ and \textbf{false} if the statement is false for
some graph $G$.

\bigskip

\bparts

\ppart[2] \quad\textbf{true}\quad\textbf{false}\quad
$R$ is symmetric.

\solution[\vspace{0.3in}]{False.}

\ppart[2] \quad\textbf{true}\quad\textbf{false}\quad
$R$ is transitive.

\solution[\vspace{0.3in}]{T}

\ppart[2] \quad\textbf{true}\quad\textbf{false}\quad
$R$ is an equivalence relation.

\solution[\vspace{0.3in}]{F}

\ppart[2] \quad\textbf{true}\quad\textbf{false}\quad
$R$ is a weak partial order.

\solution[\vspace{0.3in}]{T}

\eparts
\fi

\end{examproblem}


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

\instatements{\newpage}

\begin{examproblem}{25}

A {\em $k$-interval} is a sequence of at most $k$ consecutive natural
numbers.  Given a collection of $k$-intervals and an integer $n \geq
1$, we can construct the corresponding {\em interval graph} $G = (V,
E)$.  The vertex set $V$ is $\{1, 2, \ldots, n\}$ and there is an edge
$\{ i, j \}$ if some interval in the collection contains both $i$ and
$j$.  (Note that the graph remains well-defined even if some intervals
contain numbers larger than $n$.)

\end{examproblem}

\bparts

\ppart[5] Draw the interval graph corresponding to the collection of
4-intervals $\{ (1, 2, 3), (3, 4), (5, 6, 7, 8) \}$ and $n = 7$.

\solution[\vspace{2in}]{
\bigskip
\centerline{\resizebox{!}{0.75in}{\includegraphics{figures/interval}}}
\bigskip
}

\ppart[20] Let $G$ be an interval graph corresponding to a collection
of $k$-intervals and some integer $n \geq 1$.  Assume that $k \geq 1$.
Use induction to prove that $G$ is $k$-colorable.

\solution{The proof is by induction on $n$ with the induction
hypothesis taken from the claim.  If $n = 1$, then $G$ consists of a
single vertex, which we can surely color using at most $k \geq 1$
colors.  Now assume that the claim holds for every $n$-vertex interval
graph, and suppose that $G$ is an $(n+1)$-vertex interval graph.
Remove vertex $n+1$.  By induction, we can $k$-color the remaining
graph.  Now add back vertex $n+1$.  Since every interval contains at
most $k$ vertices, vertex $n+1$ is adjacent to at most $k - 1$ of the
preceding vertices.  Since $k$ colors are available, we can assign
vertex $n+1$ a color different from all its neighbors.  The claim
follows by induction.

(Note that when we say, ``Remove vertex $n+1$'' in the proof above, we
do not mean an arbitrary vertex; rather, we literally mean the one
identified with the number $n+1$.)}

\eparts

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

\instatements{\newpage}

\begin{examproblem}{16}
Let $R$ be a binary relation on a set $A$.  Indicate whether each
statement below is \textbf{true} or \textbf{false}.  {\em If your
answer is \textbf{false}, provide a counterexample.}  No explanation
is required for \textbf{true} answers.

\begin{problemparts}

\problempart[4] \quad\textbf{true}\quad\textbf{false}\quad
If $R$ is an equivalence relation, then $R^2 = R$.

\solution[\vspace{1.5in}]{True.  We show that $xR^2y$ if and only if
$xRy$.  If $xR^2y$, then there exists a $z$ such that $xRz$ and $zRy$.
Since $R$ is transitive, this implies $xRy$.  On the other hand,
suppose that $xRy$.  Then since $yRy$, since $R$ is reflexive.  These
two facts imply that $xR^2y$.}

\problempart[4] \quad\textbf{true}\quad\textbf{false}\quad
 $R$ is a transitive relation iff $R^2 \subseteq R$.

\solution[\vspace{1.5in}]{True.  First, suppose that $R$ is a
transitive relation and $xR^2y$.  Then there exists a $z$ such that
$xRz$ and $zRy$.  The transitivity of $R$ implies that $xRy$ as well.
Thus, $R^2 \subseteq R$.  Onthe other hand, if $xRz$ and $zRy$, then
$xR^2y$, which implies that $xRy$.  Therefore, $R$ is transitive.}

\iffalse
\problempart[4] If (the graphs of) $R$ and $S$ are nonempty, then $S
\compose R$ is nonempty.

\solution[\vspace{1in}]{False.  Counterexample: $A = B \eqdef \set{1,2},
\graph{S} \eqdef \set{(1,1)}, \graph{R} \eqdef \set{(2,2)}$.
}
\fi

\problempart[4] \quad\textbf{true}\quad\textbf{false}\quad If $R =
R^*$, then $R$ is a weak partial order.

\solution[\vspace{1.5in}]{False.  Let $A$ be any set with more than
one element, and let the relation $R$ hold between every pair of
elements.  Then $R = R^*$, but $R$ is not a weak partial order,
because it is symmetric.}

\problempart[4] \quad\textbf{true}\quad\textbf{false}\quad R is a
strict partial order iff $R$ is transitive and irreflexive.

\solution[\vspace{1.5in}]{True.  The right-to-left direction follows
by definition.  All that's needed to prove the left-to-right direction
is to show that $R$ is asymmetric.  This follows because if $aRb$ and
$bRa$, then by transitivity, $aRa$, contradicting irreflexivity.  So,
$aRb$ implies $\neg[bRa]$.}

\end{problemparts}
\end{examproblem}

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

\instatements{\newpage}

\begin{examproblem}{12} A {\em $n$-bikewheel} is a graph $G = (V, E)$.  It
consists of a cycle on the vertices $v_1, \ldots, v_n$, together with
two special vertices, $s$ and $t$, which are connected by edges to
every vertex $v_i$ and to each other.  A 6-bikewheel is shown below:

\bigskip
\centerline{\resizebox{!}{2in}{\includegraphics{figures/bikewheel}}}
\bigskip

Assume that $n \geq 3$ for all the questions below.  No proofs are
required, but partial credit may be awarded for a wrong answer if an
explanation is provided.

\bparts

\ppart[3] For which values of $n$ does an $n$-bikewheel have an
Eulerian cycle?

\solution[\vspace{1.1in}]{All odd $n$.}

\ppart[3] For which values of $n$ does an $n$-bikewheel have a
Hamiltonian cycle?

\solution[\vspace{1.1in}]{All $n$.}

\ppart[3] For which values of $n$ is an $n$-bikewheel planar?

\solution[\vspace{1.1in}]{None of them.}

\ppart[3] What is the chromatic number of an $n$-bikewheel?

\solution[\vspace{1.1in}]{4 if $n$ is even and 5 if $n$ is odd.}
\eparts

\end{examproblem}

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

\instatements{\newpage}

\begin{problem}[25]
The 6.042 course mascot, Theory Hippo, has five flowerbeds arranged in
a row:

\bigskip
\centerline{\resizebox{!}{1in}{\includegraphics{figures/flowerbeds}}}
\bigskip

Unfortunately, Theory Hippo has a problem with {\em moles}, small
furry creatures that like to dig in flowerbeds.  Each flowerbed is
always either {\em moley} (occupied by a mole) or {\em clean} (not
occupied).  Each day, Theory Hippo can make one moley flowerbed clean.
However, this action flips the state of each flowerbed adjacent to the
one that he just cleaned: a moley bed becomes clean, and a clean bed
becomes moley.  Initially, flowerbed 2 is moley and all the others are
clean.

\bparts

\ppart[7] Model Theory Hippo's mole problem mathematically as a state
machine.  Specify the states, start states, and transition relation.

\solution{The set of states consists of all 5-bit sequences, $(m_1,
m_2, m_3, m_4, m_5)$.  The $i$-th flowerbed is moley if $m_i = 1$ and
clean if $m_i = 0$.  The only start state is $(0, 1, 0, 0, 0)$.  There
is a transition from state $(m_1, m_2, m_3, m_4, m_5)$ to:

\begin{itemize}
\item $(1-m_1, 1-m_2, m_3, m_4, m_5)$ if $m_1 = 1$
\item $(1-m_1, 1-m_2, 1-m_3, m_4, m_5)$ if $m_2 = 1$
\item $(m_1, 1-m_2, 1-m_3, 1-m_4, m_5)$ if $m_3 = 1$
\item $(m_1, m_2, 1-m_3, 1-m_4, 1-m_5)$ if $m_4 = 1$
\item $(m_1, m_2, m_3, 1-m_4, 1-m_5)$ if $m_5 = 1$
\end{itemize}
}

\instatements{\newpage}

\ppart[13] Theory Hippo notices that the total number of moles in beds
1, 2, 4, and 5 seems to remain an odd number, no matter what he does.
(Note that bed 3 is excluded.)  Express this property in terms of your
model and prove that it is an invariant.

\solution[\vspace{6in}]{State $(m_1, m_2, m_3, m_4, m_5)$ has the
property if $m_1 + m_2 + m_4 + m_5$ is equal to either 1 or 3.

In order to prove that this property is an invariant, we must show
that if state $p$ has the property and there is a transition $p
\rightarrow q$, then state $q$ also has the property.  (Note that the
definition of an invariant has nothing to do with the start state!)

Suppose that state $(m_1, m_2, m_3, m_4, m_5)$ has the property; that
is, the sum $m_1 + m_2 + m_4 + m_5$ is either 1 or 3.  Note that every
transition flips the state of two flowerbeds, ignoring the middle one.
Thus, there are three cases to consider:

\begin{itemize}

\item If both flowerbeds were clean before the transition, then both
are moley afterward.  The sum must have been 1 previously, and is now
3.

\item If both were moley before, then both are clean after.  The sum
must have been 3 previously, and is now 1.

\item If one was clean and one was moley before, then one is moley and
one is clean after.  The sum is unchanged.

\end{itemize}

In every case, if the property held before the transition, it holds
after.  Therefore, the property is an invariant.
}

\ppart[5] Prove that Theory Hippo can never completely eradicate the
moles from his flowerbeds.

\solution{The invariant holds for the start state.  Therefore, by the
Invariant Theorem, the invariant holds for every reachable state.
However, if the number of moles in beds 1, 2, 4, and 5 is odd, then
the total number of moles can not be zero.  Therefore, Theory Hippo
can never eradiates the moles.}

\eparts

\end{problem}

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

\end{document}
