% plain tex

\nopagenumbers
\magnification=\magstephalf
\centerline{{\bf Theoretical Computer Science Breadth Exam - Fall 1990}}

\bigskip
This exam contains 5 problems.  You must do problems 1 and 2.  In
addition, you should do 1 of the remaining problems.

\bigskip\noindent
{\bf Problems 1 and 2 are mandatory.}

\bigskip\noindent
{\bf Problem 1.}
Let $G$ be an undirected connected graph, with $n$ nodes and $m$ edges.
For each edge $e$, let $w(e)$ be the {\it weight} of $e$.  A spanning
tree of $G$ is called a {\it minimum spanning tree} if it has the
smallest value (taken over all spanning trees $T$) of
$$
\sum_{e \in T} w(e).
$$
Similarly, a spanning tree is called a {\it min-max spanning tree} if it
has the smallest value of
$$
\max_{e \in T} w(e),
$$
for any spanning tree $T$.

\smallskip
\item{(a)}
Show that any minimal spanning tree is also a min-max spanning tree.

\smallskip
\item{(b)}
Is the converse true?  Give a proof or counterexample.

\smallskip
\item{(c)}
Give the best algorithm you can for finding a min-max spanning tree.

\bigskip\noindent
{\bf Problem 2.} Explain your answers to the following questions with
constructions or counter-examples.
\smallskip
\item{(a)} Is every regular language accepted by a
{\it nondeterministic} finite automaton whose transition diagram can
be drawn on a plane without requiring arcs to cross one another?

\smallskip
\item{(b)} Is every regular language accepted by a
{\it deterministic} finite automaton whose transition diagram can
be drawn on a plane without requiring arcs to cross one another?

\bigskip\noindent
{\bf Do 1 of the following 3 problems.}

\medskip\noindent
{\bf Problem 3.}
Let $x_1 , x_2 , \ldots , x_n$ be a sequence of non-negative real numbers.
Design an $O(n)$ algorithm to find the subsequence $x_i , x_{i+1}, \ldots,
x_j$ (of consecutive elements) such that the product of the numbers in it is maximum
over all consecutive subsequences.
The product of the empty sequence is defined as $1$.

\medskip\noindent
{\bf Problem 4.}
Consider a directed tree $T$ with root $r$.
$T$ is directed from the root to the leaves, and $children(x)$ is an ordered
list of the children of the vertex $x$.

\smallskip
\item {(a)}
Give simple recursive procedures to compute the preorder number
$pre(x)$ and the number of descendants $des(x)$ for each vertex $x$ in $T$.
($pre(x)$ denotes the order in which $x$ appears in a preorder listing of
the vertices of $T$ and $des(x)$ denotes the number of vertices in the
subtree of $T$ rooted at $x$ - you may assume that every vertex is a 
descendant of itself.)

\smallskip
\item {(b)}
Show how preorder numbers and descendant counts can be used to obtain
a constant time test for whether a given vertex in $T$ is a descendant of another.

\medskip\noindent
{\bf Problem 5.}
\smallskip
\item{(a)} Show that the intersection of a regular language and a context-free
language is always a context-free language.
\smallskip
\item{(b)} Is the intersection of 2 context-free
languages always a context-free language?


\end