\magnification=\magstephalf

\centerline{Theory of Computation}
\centerline{Breadth Exam}
\centerline{Spring 1989}

\bigskip
\noindent
Directions: Answer three questions; you must answer questions 1 and 2.

\bigskip
\noindent
1.
Consider nondeterministic finite automata whose transitions are labelled
with strings from some finite alphabet.  In particular, transitions may
be labelled with the empty string.  Give an efficient algorithm for
determining if a string is accepted by such an automaton.
For a given alphabet, your method's running time should be polynomial 
in both the length of the automaton's description and the length of 
the input string.

For each $n$, there is an $n$-state nondeterministic automaton whose 
smallest equivalent deterministic automaton has $\Omega ( 2^n )$ 
states.  Why does this not contradict your answer above?

\bigskip
\noindent
2.
An undirected graph is said to be {\sl bipartite} if its vertices can be
divided into two disjoint sets $X$ and $Y$ with the property that each
edge in the graph links a vertex in $X$ with a vertex in $Y$.

\item {a)}
Show that a graph is bipartite if and only if it has no cycles of odd
length.

\item {b)}
Give an efficient algorithm to test if a graph is bipartite.

\bigskip
\noindent
3.
A {\sl counter} is a pushdown store with  one symbol, $Z$, which can be
added (pushed) or subtracted (popped) from the store, and
a special end-of-store symbol, $B$. When $B$ is at the top
of the store, the counter has value $0$, otherwise
its value is the number of $Z$'s on the counter.

A {\sl $k$-counter machine} is a deterministic Turing machine with
a read-only input tape, $k$ counters, and no worktapes.

In one step, a counter machine can test which of its counters equal 0 and
read the symbol under the input head. Based on this information
it can move its input head left or right, add 1 to any of its counters
or subtract one from any of the counters which are not $0$.
(Note that the machine is limited to only three operations on its counters:
add 1, test if a counter equals 0; and if it does not contain 0, subtract 1.
The machine cannot, for example, compare the value of two counters).

\item {a)}
A {\sl 2-way deterministic pushdown automaton} is a
deterministic pushdown automaton that can move its input head
either one cell to the left or one cell to the right in a step.
Show that any language accepted by a 2-way deterministic pushdown 
automaton can be accepted by a 2-counter automaton.
You can assume that the stack alphabet of the pushdown automaton is $\{0,1\}$. 

\item {}
(Hint: When the stack contains $a_0 a_1 \ldots a_n$, with $a_0$ at the top of
the stack and $a_n$ at the bottom, one of the counters should have the
value  $C= \sum_{i=0}^n a_i 2^i$. Show how to use the other counter to
simulate a pop and a push operation of the pushdown automaton).

\item {b)}
Extend your construction in a) to show that any language
accepted by a deterministic two-stack automaton -- a 2-way deterministic
pushdown automaton with {\sl two} stacks -- can be accepted by a 
4-counter automaton.

\item {c)}
What is the class of languages accepted by $4$-counter automata?
Prove your answer.

\vfill
\eject

\noindent
4.
In an undirected graph, a set $X$ of vertices is said to be {\sl independent}
if no edge connects two vertices in $X$.  A {\sl vertex cover} is a set of
vertices that meets every edge.  A {\sl matching} is a set of edges, no two
of which share a common vertex.

\item {a)}
It is often stated that ``finding the largest independent set is NP-complete.'' 
Explain carefully what this means.

\item {b)}
For bipartite graphs, it can be shown that the size of
the smallest vertex cover equals the size of the largest 
matching. (You need not prove this.) Using this fact, give
a polynomial-time algorithm for finding a largest 
independent set in a bipartite graph, as follows.

\itemitem{i)}
Show that $X$ is independent iff $\bar X$ (the complement of $X$)
is a vertex cover.

\itemitem{ii)}
Give a polynomial time algorithm for
finding the size of the largest independent set.  You can assume
a polynomial-time algorithm for finding the size of the largest 
matching is available as a ``black box.'' 

\itemitem{iii)}
Now use the algorithm designed above to efficiently construct
a largest independent set.

\bigskip
\noindent
5.
A {\sl digital search tree} is a binary tree that is commonly used
in radix searching.  To store alphabetic characters in such a tree
we assign them a binary representation.  For example, we might assign
five bit numbers to each letter, giving A the binary representation
of 1 and Z the representation of 26.
The figure below shows the digital search tree that would result if
we began with an empty tree and inserted
the letters A, S, E, R, C, H, I, N, G, X, M, P, L in the order listed.
\medskip

\settabs 4 \columns
\+&{A 00001}\cr
\+&{S 10011}\cr
\+&{E 00101}\cr
\+&{R 10010}\cr
\+&{C 00011}\cr
\+&{H 01000}\cr
\+&{I 01001}\cr
\+&{N 01110}\cr
\+&{G 00111}\cr
\+&{X 11000}\cr
\+&{M 01101}\cr
\+&{P 10000}\cr
\+&{L 01100}\cr

\medskip
Notice that the branches of the search tree are labelled with 0 or 1
and that a new element is added by placing it on the path to the root
that is labelled with a prefix of its representation.
Because of this, and the fact that we assigned A the binary representation
of 1 and Z the binary representation for 26, each level of the digital search
tree contains characters that are lexicographically sorted from left
to right.

Design an algorithm that will take a digital search tree such as the one
that we have described as input and produce
as output a list containing the elements in the search tree in lexicographic
sorted order.  You may assume that the digital search tree is stored in
an array, that is, if a node is stored in location $i$ then 
its children are stored in locations $2i$ and $2i+1$ (a value of
00000 denotes an empty child).  Your algorithm should be as efficient 
as possible.

\bigskip
\bigskip
% [PASTE IN SEDGEWICK, p 216, ABOVE.]

\vfill
\eject
\pageno=1

\centerline{Theory of Computation}
\centerline{Depth Exam}
\centerline{Spring 1989}

\bigskip
\noindent
Directions: answer any four questions.

\bigskip
\noindent
1.
A {\sl 2-way probabilistic finite state automaton} (2pfa) is 
the same as a 2-way
deterministic finite automaton, except that the automaton may use coin-tosses.
That is, the choice of next state and of direction to move the head on
the input tape depends on the current state, the symbol currently under the
head and whether the coin toss is heads or tails (both are equally likely). 

Assume that the input $w$ is presented on the input tape as $\# w \#$, 
where $\#$
is a special symbol that marks the boundaries of the input. 
Initially the input head is positioned on the left $\#$. There are 
distinguished start, accepting and
rejecting states. On accepting or rejecting, the machine halts.

The language {\sl accepted} by a 2pfa is the set of all strings  $w$ such that
with $\# w \#$ on the input tape the 2pfa reaches the accepting state with
probability $\ge 1/2$. Thus for any string {\sl not} accepted by the
2pfa, the probability of reaching the accepting state is $< 1/2$.

The language $\{a^n b^n \;|\; n\ge 1\}$
is accepted by the 2pfa described as follows.

The 2pfa repeatedly sweeps the input from left to right. On the first
sweep, it verifies that the input is of the form $ a^+ b^+ $ and rejects
if the input is not of this form.
If it does not  reject on the first sweep, the 2pfa initializes to 0 two
variables $A$ and $B$, maintained in its finite state, 
and then runs the following procedure on each sweep over the input.

The coin is tossed for every input symbol encountered during the
sweep. We say the sweep {\sl produces a win} for the $a$'s ($b$'s) if all
the coins tossed while passing over the block of $a$'s ($b$'s) turn up
heads. If the sweep produces a win for the $a$'s but not for the $b$'s
then $A := A+1$. Similarly, if the sweep produces a win for the $b$'s
but not for the $a$'s, then $B := B+1$.

This is repeated until $A+B=2$. The input is accepted if 
$A=B=1$ and is rejected otherwise.

\item {a)}
Prove that the 2pfa specified by the above algorithm
accepts the language $\{a^n b^n \;|\; n\ge 1\}$.

\item {b)}
Design a {\sl one-way} probabilistic finite automaton
(pfa) that accepts the language $\{a^n b^n \; | \; n\ge 1\}$. Just as
for deterministic finite automata, a pfa can only scan the input once
from left to right.

\bigskip
\noindent
2.
A {\sl two-person pebble game} is played on the vertices of a
directed acyclic graph by two players, called the Challenger and
the Pebbler. The rules of the game are as follows.
The Challenger begins the game by challenging any vertex. 
The game now proceeds in rounds with each round consisting of a {\sl pebbling}
move followed by a {\sl challenging} move. In a pebbling move, the
Pebbler picks up zero or more pebbles from vertices already pebbled
and places pebbles on any non-empty set of vertices. In a challenging
move, the Challenger either rechallenges the currently challenged vertex, or 
challenges one of the vertices that aquired a pebble in the current round.

The Challenger loses the game at a vertex $v$ if, immediately following the
Challenger's move, $v$ is the current challenged vertex and all
immediate predecessors of $v$ have pebbles on them.

The time used by a pebble game is the number of pebble placements.
The number of pebbles used by a pebble game is the
maximum number of pebbles on the graph after any pebbling move.
A graph can be two-person pebbled in time $T$ with $p$ pebbles
if there is a winning strategy for the pebbler such that every
possible play of the game on the graph uses time at most $T$ and at
most $p$ pebbles.

\item {a)}
Show that in any $n$-leaf binary tree where $n\ge 2$,
there is a vertex $v$ such that $|v|$, the number of leaves which 
are descendants of $v$, satisfies $n/3 \le v \le 2n/3$.

\item {b)}
Use a) to show that an $n$-leaf binary tree can
be two-person pebbled with four pebbles in $O(\log n)$ time.

\item {c)}
Show how to pebble an $n$-leaf binary
tree with only two pebbles in $O(\log n)$ time.

\vfill
\eject

\noindent
3.
Consider Boolean circuits that are built of gates that implement
AND and XOR (the constants 0 and 1 are allowed).  A circuit is called
{\sl planar} if its associated digraph is planar.

Show that any Boolean circuit has an equivalent circuit that is planar.
How much larger is the planar equivalent circuit than the original circuit?


\bigskip
\noindent
4.
A set $S$ is {\sl sparse} if there is a polynomial $p$ such that for all $n$
$$\{ x \in S : |x| \le n \} \le p(n).$$

\item {a)}
Show that if $\overline {SAT}$ is polynomial many-one reducible to a
sparse set $S$, [ $\overline {SAT} \le_m^P S$ ], 
then $SAT$ is polynomially decidable.

\item {b)}
Explain why your proof for a) did not require that there be
any bound placed on the complexity of the sparse set $S$.

\item {c)}
Explain why your proof for a) does, or why it does not, show
that if $SAT$ is polynomial many-one reducible to a sparse set then $SAT$
is polynomially decidable.

If the proof you gave for a) does not prove the result stated in c),
then use the following hints to prove the result.

\item {d)}  
Show that if $SAT$ is polynomial many-one reducible to a sparse
set $S$, then $SAT$ is polynomial many-one reducible to some sparse set,
$T$, in $NP$.

\item {e)}
Assume that $SAT \le_m^P S$ where $S$ is sparse and that the reduction
is witnessed by a polynomially computable function $g$.
Instead of bounding
$|g( \overline {SAT} ~ \bigcap ~ \{ x : |x| \le n \}  ) |$
by a polynomial, as in the proof for a),
there is now a polynomial bounding function $b$ that ensures
$$|g( SAT ~ \bigcap ~ \{ x : |x| \le n \}  ) | \ \ \le\ \  b(n);$$
explain why this is true.

\item {}
Now define the {\sl pseudo-complement} of $SAT$ as
$$\eqalign{P(\overline {SAT}) =_{def} \{\langle x,t \rangle ~:~ &t
\le b(|x|) ~\& {\rm ~there~exist~distinct~}g(y_1) \ldots g(y_t) \cr
&{\rm \&~for~each~} i~~[y_i \in SAT~\bigcap ~ \{ x : |x| \le n \} {\rm ~and~}
g(y_i) \ne g(x)]\},}$$
and show $P(\overline {SAT}) \in NP.$  

\item{}
Now for each $n$, and for each $m \le b(n)$, define
$$ P(\overline {SAT})_{n,m} =_{def} \{x : |x| \le n {\rm ~and~} \langle x,m
\rangle \in P(\overline {SAT})\}.$$

\item{}
If $m_0 = |g(SAT) ~ \cap ~ \{ x : |x| \le n \}|,$
i.e., if $m_0$ happens to be the actual number of distinct elements of $S$
which elements  of length less than or equal to  $n$ in $SAT$ map to under $g,$
then show that
$$P(\overline {SAT})_{n,m_0} = \overline {SAT} ~ \bigcap ~ \{ x : |x| \le n\}.$$

Use this fact to complete the proof.

\vfill
\eject

\noindent
5.
An undirected graph is said to be {\sl bipartite} if its vertices can be
divided into two disjoint sets $X$ and $Y$ with the property that each
edge in the graph links a vertex in $X$ with a vertex in $Y$.

\item {a)}
Give an algorithm to test if a graph is bipartite.  Your algorithm 
should run in linear time.  Show that this is best possible.

\item {b)}
A graph is called {\sl tripartite} if the vertices can be divided into
three disjoint sets such that each edge links a vertex in one of these sets 
with a vertex in another, different, such set.  What can you say
about the complexity of deciding if a graph is tripartite?  Prove 
your answer.


\bigskip
\noindent
6.
In an undirected graph, a set $X$ of vertices is said to be {\sl independent}
if no edge connects two vertices in $X$.

\item {a)}
It is often stated that ``finding the largest independent set is NP-complete.'' 
Explain carefully what this means.

\item {b)}
Give an algorithm for finding a largest independent set in a bipartite 
graph.   Your algorithm should be as efficient as possible; estimate
its complexity.

\end