\def\nil{\ang{}}

\begin{examproblem}[15]

\begin{problemparts}

We usually describe \emph{rooted trees} as a kind of graphs, but we can
represent them formally as nested $n$-tuples.  Namely, rooted trees will
be defined recursively as follows:
\begin{itemize}

\item the \emph{empty tuple}, $\nil$, is a rooted tree.

\item if $T_1, T_2,\dots,T_n$ is a sequence of $n \ge 1$ rooted trees,
then the $n$-tuple $T\eqdef \ang{T_1, T_2,\dots,T_n}$ is a rooted tree.  

\end{itemize}
We define the function $\emph{numleaves}(T)$ recursively on the definition
of rooted trees:
\begin{itemize}
\item $\emph{numleaves}(\nil) \eqdef 1$,
\item $\emph{numleaves}(\ang{T_1,\dots,T_n}) \eqdef \sum_{i=1}^n \emph{numleaves}(T_i)$.
\end{itemize}

\problempart{3} Give a similar recursive definition of the function
$\emph{numinternal}(T)$ that equals the number of ``internal'' nodes of
the rooted tree $T$; that is, $\emph{numinternal}(T)$ is the number of
nodes of the tree that are not leaves.


\solution{
\item  $\emph{numinternal}(\nil) = 0$,

\item $\emph{numinternal}(\ang{T_1,\dots,T_n}) \eqdef n+ \sum_{i=1}^n
\emph{numinternal}(T_i)$.
}


\problempart{12} We also define the function $\emph{numedges}(T)$
recursively on the definition of rooted trees:
\begin{itemize}
\item $\emph{numedges(\nil) \eqdef 0$,
\item $\emph{numedges}(\ang{T_1,\dots,T_n}) \eqdef n+\sum_{i=1}^n \emph{numedges}(T_i)$.
\end{itemize}

Prove by structural induction that for any rooted tree, $T$,
\[
\emph{numedges}(T) = \emph{numleaves}(T) + \emph{numinternal}(T).
\]

\solution{TBA}

\end{problemparts}
\end{examproblem}



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