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

%% Latex asks whether or not to include solutions
\askaboutsolutions

\begin{document}

%% Practice Problems 5: Trees, Structural Induction
\ifshowsolutions
  \prsol{5}{October 1, 2001}{\stamp}
\else
  \prprob{5}{October 1, 2001}{October 3, 2001}{\stamp}
\fi

\textbf{Reading:} Rosen~\S8.1-2, 8.5, Week~5 Lecture notes.
%\emph{Supplementary reading:} Velleman~\S4.4, Rosen~\S7.1--7.4, 7.8.

\vspace{.1in}

\ifshowsolutions{}\else
By~9am on the due date, send email to
\begin{center}
\texttt{6042-probs@theory.lcs.mit.edu}
\end{center}
indicating in at most three sentences one or more of the following:
the passage in the reading---\emph{including its page number}---you
\begin{itemize}
\item found most difficult,
\item found most surprising,
\item would like to have discussed in the next Lecture.
\end{itemize}
%
%\vspace{.1in}
%
%\textbf{Problem Submission:} We are trying out a \textbf{new online tutor
%system} for submission of the pre-lecture practice problems.  You can
%access the tutor from the course website.  The online tutor will tell you
%if your answers to the problems are correct, and it will allow you to
%change the incorrect ones.
%
%This version of the tutor is a beta-release.  If you have trouble using
%the online system, feel free to submit your problem solutions on paper at
%the beginning of your tutorial section.  We would be grateful for a bug
%report on any problems with the online tutor.
\fi

\begin{problems}
  
\problem Let $W$ be a set of strings.  The language $W^+$ is
recursively defined as follows:
\begin{enumerate}
\item If $w\in W$, then $w\in W^+$.
\item If $x\in W^+$ and $w \in W$, then $xw \in W^+$.  ($xw$ is called the \emph{concatenation} of the word $x$ and the word $w$.)
\item $W^+$ contains nothing else.
\end{enumerate}

$W = \{ab, abba, a\}$

Which of the following strings are in $W^+$?
\begin{itemize}
\item        $abababba$        \solnospace{Possible}
\item        $abbab$           \solnospace{Impossible}
\item        $babba$           \solnospace{Impossible}
\item        $aaaaaab$         \solnospace{Possible}
\end{itemize}

\problem Which of the following graphs are trees?

\problempart{
\begin{center}
\includegraphics[width=1.5in,height=1.5in]{figures/pp5prob2a}
\end{center}
}

\solnospace{Not a tree}

\problempart{
\begin{center}
\includegraphics[width=1.5in,height=1.5in]{figures/pp5prob2b}
\end{center}
}

\solnospace{Tree}

\problempart{
\begin{center}
\includegraphics[width=1.5in,height=1.5in]{figures/pp5prob2c}
\end{center}
}

\solnospace{Not a tree}

\problempart{
\begin{center}
\includegraphics[width=1.5in,height=1.5in]{figures/pp5prob2d}
\end{center}
}

\solnospace{Tree}

\problem What is the chromatic number of a tree? 
\solnospace{2}

\problem Find a spanning tree for the following graph by removing
edges

\begin{center}
\includegraphics{figures/pp5prob4}
\end{center}

\solnospace{It can be done in several ways, for example removing $(b
  d), (c e)$.}

\end{problems}

\end{document}


