\magnification = \magstep1
{ \bf
\centerline { Theory of Computation }
\centerline { Qualifying Exam }
\centerline { Spring 1996 }
}

\bigskip
{\bf Directions.}  There are six questions.  Answer any four.

\bigskip
\item{1.}
Consider the following parallel version of quicksort, performed
by 2 processors. 

\smallskip
\itemitem{}
In the partitioning step, the pivot element
is chosen randomly and uniformly from the set of elements to be
sorted.  Once the problem is partitioned, processor 1 
solves one of the two subproblems and processor 2 solves the other, both 
working sequentially and independently of each other.

\smallskip
\item{}
Assume that the number of comparisons performed by each processor
in the partitioning step is exactly $n/2$; that is, perfect parallelism 
is achieved in distributing the comparisons between the two processors.  
(You need not be concerned about how this is done.) 

\smallskip
\item{}
Compute a lower bound on the expected maximum number
of comparisons, where the maximum is taken over the two processors.
The leading term of your lower bound should be explicit (no hidden
constants).

\bigskip
\item{2.}
Prove that the following problem is NP-complete:
Given a formula in conjunctive normal form with 3 literals per clause,
and a number $k$, is there a truth assignment to the variables that 
sets at least $k$ clauses to false?

\bigskip
\item{3.}
In this problem you are to consider data structures similar to
heaps, which instead of extracting the mimimum element, extract
the median.  Assume that the elements inserted into the data
structure have a key from some totally ordered set.
Design a data structure $D$ that supports the following operations
efficiently:

\smallskip
\itemitem{}
insert($D,x$): insert the element $x$ into data structure $D$;

\smallskip
\itemitem{}
extract-median($D$): remove the median element from $D$.

\smallskip
\item{}
Prove a bound on the worst-case running time of each operation.

\bigskip
\item{4.}
For this problem you are to consider the complexity of computing the 
$n$-th row of Pascal's triangle; that is, finding the $n+1$ quantities
$$
{n \choose 0}, {n \choose 1}, \ldots,  {n \choose n-1}, {n \choose n}.
$$
You may assume that the recurrence relation
$$
{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}
$$
is used.

\smallskip
\itemitem{a)}
Explain why the usual ``uniform cost'' model, in which an arithmetic
operation takes one step, is not appropriate here.

\smallskip
\itemitem{b)}
Assume that $m$-bit integers can be added or subtracted in $m$ steps.
As a function of $n$, what is the cost of computing the $n$-th row?

\bigskip
\item{5.}
Classify the following formal language (regular, context-free,
context-sensitive):
$$
L = \{ a^q : \hbox{$q$ is a prime power} \}.
$$
(The first few elements of $L$ are $a^2, a^3, a^4, a^5, a^7, \ldots$.) 
Prove your claims.

\bigskip
\item{6.}
M. Fellows and N. Koblitz have recently published a deterministic
polynomial time algorithm $A$ with the following remarkable property.
When given binary encodings of a number $n$ and the prime factorization of 
$n-1$, $A$ correctly determines whether $n$ is prime or composite.

\smallskip
\itemitem{a)}
Use this result to prove that the set of primes (given in binary notation)
is in $\hbox{NP} \cap \hbox{co-NP}$.  Explain why the same is true of
the language
$$
F = \{ (n,b) : \hbox{$n$ has a nontrivial factor $< b$} \},
$$
which is a decision problem related to integer factoring.

\smallskip
\itemitem{b)}
Exhibit a particular deterministic polynomial-time algorithm that 
correctly decides membership in $F$, if any polynomial-time algorithm
does.  (Hint: First show, using $A$, that there is an algorithm
for $F$ producing a witness of membership or non-membership as output.)

\end