% plain tex

\magnification=\magstephalf

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

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

\bigskip
\noindent
1.
In the analysis of algorithms we normally measure the time complexity
of an algorithm as a function of the size of the input.  Most frequently
we study the worst case behavior of algorithms, although in practice
average behavior is often more important.

\item {a)}
Give an example of a problem and an algorithm for solving it that
requires $C n^2$ operations (for some $C>0$ and all sufficiently large
input sizes $n$) in {\it both} the worst case and the average case. 

\item {b)}
Give an example of a problem and an algorithm for solving it that
requires $C n^2$ operations (for some $C>0$ and all sufficiently large 
input sizes $n$) in the worst case
but requires fewer operations for the average case.

\bigskip
\noindent
2.
NP-complete problems are often called ``intractable problems.''
Nevertheless, they arise in practice and must be solved.

\item {a)}
What is your planned research area?

\item {b)}
Give an example of an NP-complete problem that arises in your
research area.

\item {c)}
Explain what impact the NP-completeness of this problem has on the
way this problem is solved in practice.

\bigskip
\noindent
3.
A two-dimensional square array of integers is said to be 
{\it block-diagonal} if its nonzero entries consist of a
number of square subarrays written one after the other down the 
diagonal.  (The squares need not all have the same size;
note that we count a $1 \times 1$ array as a square.)
For example, the first array
written below is block-diagonal, but the second is not.
$$
\pmatrix{ 1 & 2 & 0 & 0 & 0 \cr
          3 & 4 & 0 & 0 & 0 \cr
          0 & 0 & 5 & 6 & 0 \cr
          0 & 0 & 7 & 8 & 0 \cr
          0 & 0 & 0 & 0 & 9 \cr }
\qquad\qquad
\pmatrix{ 1 & 0 & 1 & 0 & 1 \cr
          0 & 1 & 0 & 1 & 0 \cr
          1 & 0 & 1 & 0 & 1 \cr
          0 & 1 & 0 & 1 & 0 \cr
          1 & 0 & 1 & 0 & 1 \cr }
$$
Design a data structure for storing block-diagonal arrays.
It should have the following properties: 
\smallskip
\itemitem{i)}
It should be possible
to access any element in $O(1)$ time. 
\smallskip
\itemitem{ii)}
If the array has
$m$ nonzero entries, the total space used is $O(m)$. 
\medskip
Note. Your solution may be difficult to express in a high-level language such
as Pascal.  For this reason, you should think of the memory available
to you as a large one-dimensional array of cells, each of which can hold
an integer, a pointer, etc.  Your data structure should use $O(m)$ 
{\it contiguous} cells of this memory.

\vfill
\eject

\bigskip
\noindent
4.
>From the following list of languages, select a language that
is regular and prove this.  Select a language that is context-free,
but not regular, and prove this also.  Finally, identify a language
that is NP-complete.

\item {a)}
The set of all Boolean formulas that are tautologies.

\item {b)}
The set of all Boolean formulas that are not tautologies.

\item {c)}
The set of all Boolean formulas that are in conjunctive
normal form, with exactly three literals per clause.

\item {d)}
The set of all strings $x$ such that $xx$ is a palindrome.

\item {e)}
The set of all strings $x$ such that $xx$ is not a palindrome.

\item {f)}
All positive integers (expressed in binary) whose remainder, when divided
by 7, is greater than 3.


\vfill
\eject
\pageno=1

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

\bigskip
\noindent
Directions: There are five questions.  You must answer three of them.

\bigskip
\noindent
1.  Show that the multi-processor scheduling problem, 
described below, is NP-complete.

\item{}
Given a set of jobs $J = \{j_1, j_2, \ldots , j_n\}$, a directed acyclic graph
$G = (J,E)$ (denoting the precedence constraints among the jobs),
a number $m$ (the number of machines) and an integer $T$ (the deadline),
is there a way to schedule the $n$ jobs on the $m$ machines so that
the precedence constraints are satisfied and no machine is assigned
more than $T$ jobs?

\bigskip
\noindent
2.  The following algorithm produces a random permutation of $n$ elements
in an array $A$:

\def \tabber{xxxxxx}
$$
\vbox{
\tt
\settabs\+\tabber&\tabber& \cr
\+	procedure randompermute1(A[1..n]); \cr
\+&	   begin \cr
\+&	   for j := 1 to n-1 do \cr
\+&&	      s:= randominteger(j,n); (* a random integer between j and n *) \cr
\+&&	      swap(A[j], A[s]); \cr
\+&	   end; \cr
}
$$


\item{a)}
Prove that this algorithm is correct.

\item{b)}
In parallelizing this algorithm, a useful property is that
the swaps do not have to be done in sequential order, from 1 to $n$
as in the above {\tt for} loop. Prove this.

\item{c)}
Another algorithm for producing a random permutation is the
following divide-and-conquer algorithm (assume $n$ is a power of 2):

\def \tabber{xxxxxx}
$$
\vbox{
\tt
\settabs\+\tabber&\tabber&\tabber&\tabber \cr
\+	procedure randompermute2(A[1..n]); \cr
\+&	   begin \cr
\+&	   if n > 1 then \cr
\+&&	      randompermute2(A[1..n/2]); \cr
\+&&	      randompermute2(A[(n/2)+1..n]); \cr
\+&&	      for i := 1 to n/2 do \cr
\+&&&		 with probability 1/2, swap(A[i], A[i+(n/2)]); \cr
\+&	   end; \cr
}
$$

\item{d)}
Prove that this algorithm is correct.
Why is this algorithm less efficient than {\tt randompermute1}?
\itemitem{}
[Note:  We blew it!  Not only is this algorithm less efficient
than {\tt randompermute1}, it does {\bf not} produce a random
permutation.  Prove this instead.] 

\item{e)}
A natural approach to parallelize the algorithm of part (c) to run
on a $p$-processor machine, is to break the array $A$ down into
$p$ contiguous groups, and assign one processor to permute 
each group sequentially.  
Assume for simplicity that $p$ divides $n$, and let $k = n/p$.
Then randomly pair the groups.
If $A[i, i+k]$ and $A[j,j+k]$ are paired, with probability 1/2,
swap $A[i+l]$ and $A[j+l]$ for each $l$,  $0 \le l \le k$.
Explain why this approach does not yield a random permutation.

\vfill
\eject
\bigskip
\noindent
3.
The following algorithm for finding the maximum of $n$ elements was
proposed by Valiant. Prove that the running time for this algorithm on
the CRCW (concurrent read, concurrent write) PRAM model is $O(\log\log n)$
with $p = n$ processors.

The algorithm operates in stages; at the $s$th stage there are $n(s)$
distinct input values 
$$a_1, a_2, \ldots , a_{n(s)}.$$  
At the first stage, the
input values are the $n$ inputs to the problem and $n(1) = n$.  The input
values are partitioned into the fewest number $r$ of sets 
$S_1, S_2, \ldots, S_r$ of essentially equal size 
(i.e. the absolute value of $|S_i| - |S_j|$ is $\le 1$), such that
$$
\sum _ {i = 1} ^ r {|S_i| \choose 2} \le p .
$$

To each set $S_i$, ${|S_i| \choose 2}$ processors are assigned so that
each processor compares one of the ${|S_i| \choose 2}$ distinct pairs of
elements. The result of the comparison is recorded in an auxiliary
Boolean array $b_1, \ldots , b_{|S_i|}$, which is initialized to all 1's at
the start of the stage.  Processor $p$ assigns 0 to $b_k$ where $k$ is the
index of the smaller element of the pair $p$ compares. (Concurrent write
is used here).  The winners of a set $S_i$ is the sole element $a_l$ with
$b_l = 1$.  The winners of one stage are the input values of the next
stage, until there is one winner, which is the maximum of the whole
set.

\bigskip
\noindent
4.
For this problem you are to consider the randomized version of
Hoare's Quicksort algorithm, which sorts $n$ elements by first 
choosing a random element $x$ from among these elements, grouping
the remaining elements into those less than $x$ and those greater than $x$,
and recursively sorting these two smaller lists. 
\medskip
Assume that to make a random choice from a set of size $N$ requires
$\log_2 N$ random bits.  How many random bits, on average, are used
by the above randomized Quicksort algorithm?  Work out your answer
as precisely as you can.

\bigskip
\noindent
5.
Let $DSPACE(f)$ denote the set of languages recognizable by
a deterministic multitape Turing machine that uses $\le f(n)$
work space on inputs of length $n$.  We define $NSPACE(f)$ and 
$ATIME(f)$ similarly, using nondeterministic and alternating
Turing machines respectively.

\smallskip
\item{a)}
Prove that $NSPACE(\log n)$ is contained in $ATIME(\log n)$.

\smallskip
\item{b)}
Prove that $ATIME(\log n)$ is contained in $DSPACE(\log^2 n)$.

\end