\magnification=\magstephalf

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

\bigskip
\noindent
Directions: There are six problems.  Answer any four.

\bigskip
\noindent
{\bf 1.}
Let $\Sigma = \{ 0,1 \}$. A language $L$ in $\Sigma ^ *$ 
is called {\sl prefix-free} if
no proper prefix of a string in 
$L$ is also in $L$.  (If $x$ is
a string, a proper prefix of $x$ is a string $y$ with $|y|<|x|$ for which
$x = yz$ for some $z$.)

\item{a)}
Give an example of a language that is prefix-free and 
another language that is not.

\item{b)}
Show that if $L$ is prefix-free, then 
$$
\sum _{x \in L} {1 \over 2^{|x|} } \le 1 .
$$

\item{c)}
Give an example to show that this can be false if $L$ is not prefix-free.

% b) is called the Kraft inequality.

\bigskip
\noindent
{\bf 2.}
The standard queue operations are:

\item{$\bullet$}
{\sl enqueue(Q, d)}: places $d$ on queue $Q$, 

\item{$\bullet$}
{\sl dequeue(Q, d)}: removes the least recently enqueued
element of $Q$ and returns it in $d$, and

\item{$\bullet$}
{\sl empty(Q)}: a Boolean function that returns true when $Q$ is
empty and false otherwise.

\smallskip
\noindent
Similarly, the standard stack operations are:

\item{$\bullet$}
{\sl push(S, d)}: places $d$ on stack $S$,

\item{$\bullet$}
{\sl pop(S, d)}: removes the most recently pushed
element of $S$ and returns it in $d$, and

\item{$\bullet$}
{\sl empty(S)}: a Boolean function that returns true when $S$ is
empty and false otherwise.

\smallskip
Show how to implement the three queue operations above
using two stacks 
so that, if any $k$ queue operations are performed,
the total number of stack operations is at most $O(k)$.
(The elements in the two stacks should make up the queue, and
each queue operation should be ``simulated'' with 
appropriate stack operations.)
Explain why your implementation achieves the desired performance.

\bigskip
\noindent
{\bf 3.}
Give examples of languages in each of the following classes:

\item{a)}
P, the class of polynomial-time recognizable languages,
\item{b)}
the class of NP-complete languages,
\item{c)}
the class of languages in NP that are thought unlikely to be NP-complete,
\item{d)}
the class of languages that are not in NP, but are recursive,
\item{e)}
the class of recursively enumerable languages that are not recursive.

\bigskip
\noindent
{\bf 4.}
The maximum bipartite subgraph problem is:
Given a graph $G$ and an integer $k$, does $G$ have a
bipartite subgraph with at least $k$ nodes?

Prove that this problem is NP-complete.
(Hint: try reducing the maximum independent set problem to it
in the following way.
Given a graph $G$ and an integer $k$, construct a new graph $G'$
with twice as many nodes as $G$, such that $G'$ has a
bipartite subgraph of size $2k$ if and only if $G$ has an
independent set of size $k$.)

\vfill
\eject

\bigskip
\noindent
{\bf 5.}
For this problem we will say that a tree is a {\it binary tree} if each
node in the tree has 0, 1 or 2 children.  For a tree $T$ we will denote
the number of nodes in $T$ by $\#(T)$ and for a node $d$ we will denote
the subtree rooted at $d$ by $T_d$.

Design an algorithm which takes as input a binary
tree and returns as output a node $d$ from the input tree such that the
following holds when $\#(T)$ is sufficiently large:
$$ {1 \over 3}\#(T) ~~\le~~ \#(T_d) ~~\le~~ {2 \over 3} \#(T).$$
Your algorithm should run time in $O(\#(T))$ and use as little additional
storage as possible.

\bigskip
\noindent
{\bf 6.}
Let $A(n)$ denote the average number of comparisons made by insertion sort
for an input array of size $n.$
It is not difficult to show that $A(n)$ is $O(n^2)$.  However, the
simplicity of the insertion sort algorithm also makes it possible to
calculate fairly exactly the function $A(n)$.  For this problem you
are to calculate it as exactly as you can.
You may assume that the the input array does not contain
duplicate entries and that all input permutations are equally likely.

\vfill
\eject
\pageno=1

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

\bigskip
\noindent
Directions:  There are six questions.  Answer any three.

\bigskip
\noindent
{\bf 1.}
A {\it Euclidean graph} is a graph whose nodes have 2-dimensional Euclidean
co-ordinates associated with them.
A {\it triangulation} is a connected planar Euclidean graph whose 
straight-line edges divide the region of the plane enclosed by the graph into
triangular regions.
The {\it greedy triangulation} of a point set is the triangulation formed
by successively adding the shortest possible edge to the already formed
graph while maintaining the invariant that the graph is planar.

Show that the minimum spanning tree for a 2-dimensional Euclidean
point set is always a subgraph of the greedy triangulation.

\bigskip
\noindent
{\bf 2.}
Let $M$ be an $n$-by-$n$ matrix with entries chosen from some
field (for example, the real numbers).  Let $k$ be a positive
integer.  Using the ordinary
algorithm for matrix multiplication, and repeated squaring,
roughly how many arithmetic operations are needed to compute $M^k$?

Can you think of a way to compute $M^k$ that will use fewer operations
when $k$ is large compared to $n$? How large must $k$ be for your
method to be an improvement on the algorithm described
above?

[Hint: A matrix satisfies its own characteristic equation.]

\bigskip
\noindent
{\bf 3.}
An $n$-variable branching program is a
directed acyclic graph, where all nodes are labeled with a
variable from the set $\{x_1, \ldots, x_n\}$.
The nodes are arranged in rows, with all edges from nodes at the $i$th
row going to nodes at the $(i+1)$st row.
All nodes except those in the last row have outdegree two, with
one edge from each node labeled 0 and one labeled 1.
There is a special start node, which is in the first row,
and a special accept node in the last row.

Any binary string $w_1 \ldots w_n$ defines a path in the
branching program from the start node in the following way.
The first node in the path is the start node.
If $v$ is a node in the path that is
labeled with the variable $x_k$, then the next
node in the path is defined to be the node reachable from $v$ on 
the edge labeled $w_k$, if $v$ is not in the last row.
Otherwise $v$ is the last node on the path.  (Note that the
path might be longer than the string.)

This model is used to define language acceptance in the following way.
A string $w_1 \ldots w_n$ of length $n$ is accepted by the
branching program if and only if the associated path leads to the
sink node.
A family of branching programs ${\cal B} = \{B_0, \ldots, B_n, \ldots\}$
accepts a language $L$ if and only if for every $n$, $B_n$ is an
$n$-variable branching program and accepts exactly the strings 
of $L$ of length $n$.

Resources of a branching program are its size and its width.
${\cal B}$ has {\sl bounded width } if there is a constant $b$ such that
for every $n$, the maximum number
of nodes in any row of $B_n$ is at most $b$.
${\cal B}$ has {\sl size} $f(n)$ if for every $n$, the number of nodes of
$B_n$ is at most $f(n)$.

\item {a)} 
Show that each language in $AC^0$ is accepted by a family of
polynomial size, bounded width branching programs, where $AC^0$ is the
class of languages accepted by constant depth, unbounded fan-in
circuits with {\sl and}, {\sl or} and {\sl not} gates.

\item {b)}
Show that any language over the alphabet 
$\{0,1\}^*$ that is accepted by an
$s(n)$-space bounded deterministic Turing machine 
is accepted by a family of branching programs with size $2^{O(s(n))}$.
Do you think the converse is true?

\item{c)}
How would you define a nondeterministic branching
program, to extend the result of part (b) to
nondeterministic Turing machines?

\vfill
\eject

\bigskip
\noindent
{\bf 4.}
Fortune proved that if $\overline {SAT}$ is polynomially many-one
reducible to a polynomially sparse set, then P = NP.  His proof was based
on an algorithm that did a depth-first search and pruning of the
self-reduction trees of Boolean formulas.  The fact that his algorithm
used depth-first search turns out to be irrelevant.  Your job is to prove
that an algorithm based on breadth-first search also works.  The algorithm
is given below.

{\sl Preliminaries.}
Assume that $\overline {SAT}$ is polynomially many-one reducible to a sparse
set.  Call the sparse set $S$ and call the
reduction $f.$ Let $p(n)$ be a polynomial bound on the number of elements
of $S$ that Boolean formulas of length less than or equal to $n$ can be
mapped to.  I.e., $p$ is a composition of the polynomial bound on the
census of $S$ and a polynomial stretching factor from the reduction.

{\sl Algorithm.}
To decide whether a Boolean formula $b$, of length $n$,
is in $SAT$ we perform a breadth-first search of its self-reduction tree.
We search the tree level by level.  As we search a level
we build up a list of nodes whose children will be searched
at the next level.  For the algorithm to run in polynomial time we
need to make sure that at each level this list contains only a polynomial
number of nodes.  To do so we keep a counter
which is set to 0 at the beginning of the search over each level.

Searching a level:
When a node $x$ is visited we compute $f(x).$  If $f(x)$ is distinct from any
other element in the range of $f$ that we have found AT THIS LEVEL, then
we increment the counter and add $x$'s children to the list of nodes to be
visit at the next level. (If $f(x)$ is not distinct, then we do nothing and
thus $x$'s children will not be visited when we seach the next level.)
If the counter value is greater than $p(n),$
then we stop the entire algorithm and report that $b$ is satisfiable,
otherwise we consider the next node on the level.
When a level is completed we go on to the next level, resetting the counter.

When/if the bottom level of the tree is reached we test to see whether
any of the assignments corresponding to the leaves that remain are satisfying
assignments.  We report that $b$ is satisfiable if we find
a satisfying assignment among these assingments, and otherwise report
that it $b$ is unsatisfiable. 

\medskip
{\sl Your job.}
Prove that the above algorithm runs in polynomial time and correctly
decides membership for $SAT.$

\bigskip
\noindent
{\bf 5.}
The maximum bipartite subgraph problem is:
Given a graph $G$,
find a bipartite subgraph of $G$ with the maximum number of nodes.
The associated decision problem is: Given a graph $G$
and an integer $k$, does the maximum bipartite subgraph of $G$ have at least
$k$ nodes?

\smallskip
\item{a)} 
Show that this decision problem is NP-complete (try reducing the
maximum independent set problem to it).
\smallskip

\noindent
For many NP-complete graph problems, if the class of graphs allowable
as input is
restricted, the problem is polynomial-time solvable.  Suppose ${\cal
G}$ is a class of graphs for which a maximum independent set can be
found in polynomial time.  The following algorithm attempts to use
this fact to find the maximum bipartite subgraph for a graph in ${\cal
G}$. Given a graph $G \in {\cal G}$ as input, the algorithm simply
finds a maximum independent set, deletes it, finds another
maximum independent set in the remaining graph and outputs the
bipartite subgraph induced by the two independent sets.

\item{b)} 
Show that this algorithm does not always work in general. That is,
construct a graph $G$ for which the algorithm outputs a bipartite
subgraph which is not the maximum bipartite subgraph of $G$.

\item{c)}
Show that this algorithm does however provide a good {\sl
approximation} to the maximum bipartite subgraph, in the following
sense. Let $R_G$ denote the ratio of the size of the the graph output
by the algorithm on input $G$ to the size of the maximum bipartite
subgraph of $G$.  Show that for all graphs $G$, $R_G \ge 1/2$. Can you
show that $R_G \ge 3/4$ for all $G$?

\vfill
\eject

\bigskip
\noindent
{\bf 6.}
Consider the following (not very efficient) strategy for card
shuffling.  Start with a deck of $n$ cards in sorted order.
Repeatedly apply the following operation: take the top card, and place it
at a randomly chosen position in the deck.  This is to be repeated
until the original bottom card appears on top, at which time 
the insertion operation is done once more and the process stops.

\item{a)} 
Show that the expected number of operations until the process 
is completed is $O(n \log n)$.  

[Hint: consider the times at which the original bottom card 
changes position.]

\item{b)} 
Show that when the process is finished, all $n!$ permutations
of the original deck are equally likely.

\item{c)} 
Show that if the operation is applied a predetermined number
of times, say $k$, then the deck is not placed into random order.

% [Note: c) occurred on a previous exam!]


\vfill
\eject
\end