\problemdata      
        {?} % latex-friendly label for the prob.
        {Computational Processes, Graphs-Trees} % The topic(s) of the problem content.
        {?} % Source (if known)
        {Fall 2001, final} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).



\begin{problem}
In tutorial we considered algorithms for coding a numbered
tree as a sequence of numbers and vice-versa.  In this problem we consider
methods to prove properties of a procedure for extracting the tree coded by
a number sequence.  The trees are undirected and unrooted.

The procedure will construct a tree with $n$ vertices numbered
$1,\dots,n$ from an input that is a sequence, $s$, of $n-2$ numbers
each between $1$ and $n$.  The procedure works by adding edges to a
graph, $G$, with vertices $1,\dots,n$, deleting elements from a set,
$I$, of vertices called the \emph{incomplete vertices}, and deleting
successive elements of a sequence, $t$, of numbers.

Given input $s$, the procedure goes as follows:
\begin{enumerate}

\renewcommand{\labelenumi}{P\arabic{enumi}.}
\renewcommand{\labelenumii}{P\arabic{enumi}.\arabic{enumii}}

\item Initialize $G$ to be the graph with vertices $\set{1,\dots, n}$
and no edges, where $n \eqdef \abs{s}+2$.  Initialize $t \eqdef s$ and
$I \eqdef \set{1,\dots,n}$.

\item Repeat the following loop of instructions until there remain exactly
two incomplete vertices, that is, until $\card{I} = 2$:

\begin{enumerate}
\item Let $l$ be the largest vertex in $I$ that does not occur in $t$.

\item $I \eqdef I - \set{l}$.

\item Add the edge $(l, \text{first}(t))$ to $G$,
where \text{first}(t) is the first number in $t$.

\item $t \eqdef \text{rest}(t)$, where $\text{rest}(t)$ is the sequence of
numbers in $t$ after the first.
\end{enumerate}

\item Add to $G$ the edge between the remaining two vertices in $I$ and
terminate.

\end{enumerate}
\bparts

\ppart 
Is this algorithm deterministic or nondeterministic?  No
explanation necessary.

\solution{Deterministic}

\ppart Draw the graph generated by the following code: 72357

\ifshowsolutions \else \vspace*{2in}\fi

\solution{Will draw these in.}

\ifshowsolutions \else \newpage \fi

\ppart\label{alg-invs} For each of the following derived variables,
indicate whether, from one time around the loop to the next, it is
\begin{itemize}
\item[\textbf{I}] Increasing
\item[\textbf{D}] Decreasing,
\item[\textbf{C}] Constant,
\item[\textbf{NI}] Nonincreasing but not constant or decreasing,
\item[\textbf{ND}] Nondecreasing but not constant or increasing,
\item[\textbf{N}] or None of these.
\end{itemize}
For example,
\begin{quotation}\noindent
\vspace{-.4in}
\begin{itemize}

\item $\abs{t}$  \hfill\brule{1in}D.

\item $\card{E_G} \bmod 2$, where $E_G$ is the set of edges of
$G$. \hfill\brule{1in}N.

\end{itemize}
The length of $t$ is decreasing because its first element is removed each
time around the loop.  The parity of the number of edges of $G$ has none
of the other growth properties because edges are added one at a time
around the loop, so it alternates between 0 and~1.
\end{quotation}
This is a short-answer question, so do \textbf{not} include explanations
like the ones above.

\begin{enumerate}

\addtolength{\leftskip}{0.25in}%
% Change this next line to modify numbering style.
% Current style: roman numeral followed by )
\renewcommand{\labelenumi}{\roman{enumi})}

\item the number of vertices of $G$.  \hfill\brule{1in}

\solution{
C; the vertices are always $\set{1,\dots,n}$.
}

\item $\card{E_G}$, the number of edges in $G$.  \hfill\brule{1in}

\solution{I; an edge is added each time around}

\item
$\card{I}$, the number of incomplete vertices. \hfill\brule{1in}

\solution{D; a vertex is removed each time around.}

\item
$\card{I} - \abs{t}$, the number of incomplete vertices, minus the length
of $t$. \hfill\brule{1in}

\solution{C; always equals 2.}

\item $\card{\text{nums}(t)}$, where $\text{nums}(t)$ is the set of numbers
that occur in $t$. \hfill\brule{1in}

\solution{NI; stays the same when the first element of $t$ occurs in $t$
more than once.}

\item the number of vertices of $G$ not touching an edge.
\hfill\brule{1in}

\solution{NI; won't decrease when two nonisolated components are
connected.}

\iffalse
\item the predicate: $\text{nums}(t) \subset I$. \hfill\brule{1in}
\solution{C: always true.}
\fi

\iffalse
\item $\card{I-\text{nums}(t)}$, the number of incomplete elements that do
not appear in $t$. \hfill\brule{1in}
\solution{NI; stays the same when the first element of $t$ is not
repeated.}
\fi

\iffalse
\item
$\card{E_G} + \card{I}$ \hfill\brule{1in}
\solution{C; always equals $n$; but not obvious.}
\fi


\iffalse
\item the number of connected components of $G$ minus $\card{I}$.
\hfill\brule{1in}
\solution{C; equals 0}
\fi


\item
the number of connected components of $G$. \hfill\brule{1in}

\solution{D; but not obvious.

The problem statement says the result is a numbered tree, so $G$ has one
connected component on termination.  But $G$ initially has $n$ components,
and adding an edge can only reduce the number of components by one and
there are only $n-1$ edges in the final tree, so
the edge added each time around the loop must reduce the number of
compoennts.

Proving this without assuming that the final result is a tree needs a more
general invariant that each connected component contains \emph{exactly}
one incomplete element.  Since only edges between incomplete elements are
added, this implies that when an edge is added, it connects different
components.}

\iffalse
\item the maximum number of vertices in $I$ in any connected component of
$G$. \hfill\brule{1in}
\solution{C; always 1}
\fi

\item the number of cycles in $G$. \hfill\brule{1in}

\solution{C; always 0}

\addtolength{\leftskip}{-0.25in}%
\end{enumerate}

\ppart How many edges are in $G$ when the procedure terminates?
\hfill\brule{1in} 

\solution{$n-1$ or $\card{s}+1$} 

\ppart How many connected components does $G$ have on termination?
\hfill\brule{1in}

\solution{1}

\ppart How many possible trees are there with vertices numbered
$\set{1,\dots, n}$? \hfill\brule{1in}

\solution{$n^{n-2}$}

\eparts
\end{problem}