% plain tex

\magnification = \magstep1

\centerline{Theory of Computing}
\centerline{Breadth Exam}
\centerline{Spring 1993}

\bigskip
Directions: There are five questions, of which you must do THREE.

\bigskip
\item{1.} 
Let $M$ be a deterministic finite automaton.
Suppose that $x$ is an {\it infinite} word made up of letters
from $\Sigma$, the input alphabet of $M$. 
More precisely, $x$ is an infinite sequence of elements chosen from $\Sigma$.
We say that $M$ {\it accepts} $x$ if, when started in its
initial state and given the letters of
$x$ in order, $M$ passes through an accepting state infinitely
many times.  The language accepted by $M$ is the set of all infinite
words which $M$ accepts.  Finite automata used in this fashion
are called {\it $\omega$-automata} in the literature.

\smallskip
\item{}
State and prove a generalization of the ``pumping lemma'' for 
$\omega$-automata; i.e. applicable to the above situation.

\bigskip
\item{2.} 
The Euclidean Traveling Salesman problem is the problem of
finding a shortest tour of $n$ distinct points on the plane.
(For simplicity, assume no two points have the same $x$ coordinate).
It is well known that the Euclidean Traveling Salesman problem is
NP-hard.

% Comment: not known to be in NP for integer lattice points as
% input.

\smallskip
\item{}
Suppose we restrict our attention to ``bitonic'' tours, that is,
tours which start at the leftmost point, go strictly left to
right to the rightmost point, and then go strictly right to
left back to the starting point.

\smallskip
\item{}
Describe an $O(n^2)$ time algorithm for determining an optimal
bitonic tour.  [Hint: dynamic programming.]

\bigskip
\item{3.} 
Consider a parallel computer with a large number of processors.
In one time step, a processor can do exactly one of the following
operations: send a message to some other processor, or add two numbers.
Your objective is to form the sum of as many numbers as possible
in $m$ time steps.  At the end of your algorithm, one processor should
know the result (the sum).
You are allowed to use as many processors as you like, and you may assume
any suitable distribution of the inputs among processors; inputs
are not duplicated.

\smallskip
\itemitem{a)}
How many numbers can you add in $m$ steps using a ``binary tree''
style algorithm? 

\smallskip
\itemitem{b)}
Can you do better?

\bigskip
\item{4.} 
Given a set $Q$ of points in the plane, we define the {\it convex layers} 
of $Q$ inductively. The first convex layer of $Q$ consists of those
points in $Q$ that are vertices of the convex hull of $Q$, denoted by
CH($Q$). For $i>1$, define $Q_i$ to consist of those points in $Q$
with all points in convex layers $1,2 \ldots, i-1$ removed. Then, the
$i$th convex layer of $Q$ is CH($Q_i$) if $Q_i$ is not empty, and is
undefined otherwise.

\smallskip
\itemitem{a)}
Give an $O(n^2)$ time algorithm to find the convex layers of a set 
of $n$ points.  Your algorithm should output the points in each layer
in their natural order, say clockwise.

\smallskip
\itemitem{b)}
Give an $\Omega(n \log n)$ lower bound for this problem.

\vfill
\eject

\bigskip
\item{5.} 
A context free grammar is in {\it Chomsky normal form} if all
productions are of the form $X \rightarrow YZ$ or $X \rightarrow a$
where $X,Y,Z$ are non-terminals and $a$ is a terminal.
Define the {\it size} of a grammar to be the number of nonterminals
plus the number of terminals. 

\smallskip
\itemitem{a)}
Convert the following grammar into Chomsky Normal Form:
$$
S \rightarrow CB
$$
$$
S \rightarrow CBBC
$$
$$
C \rightarrow aaa
$$
$$
B \rightarrow b .
$$

\smallskip
\itemitem{b)}
Give a method for converting grammars to Chomsky normal form.
For your method, how large can the converted grammar be, if the
original grammar has size $n$?  Give an example showing
your estimate is best possible up to constant factors.
