\documentstyle[11pt,fullpage]{article}

\setlength{\parindent}{0pt}
\setlength{\parskip}{7pt plus 1pt}

\begin{document}
\begin{center}
{Theory of Computation} \\
{Breadth Exam}\\
{Spring 1990}
\end{center}

Directions: Answer any FOUR of the six questions below.
\begin{enumerate}
\item
For each of the following three models of computation, explain
whether or not the nondeterministic version of the model is more
powerful (i.e.\ accepts more languages) than the deterministic
version.

a)  Deterministic finite state automata versus nondeterministic
finite state automata

b)  Deterministic pushdown automata versus nondeterministic
pushdown automata

c) Deterministic 2-stack pushdown automata versus
nondeterministic 2-stack pushdown automata

In each case, if you think the nondeterministic and deterministic
versions of the model are equivalent, explain why. If you think
the nondeterministic version is more powerful than the deterministic
version, give a language accepted by the nondeterministic version but
{\sl not} by the deterministic version.

Notes: 
You can assume in all three cases that the input head never moves to the left.

A 2-stack pushdown automaton is defined just as a regular (1-stack)
pushdown automaton, except that at each transition, 2 stacks are
modified. That is, each transition of a 2-stack pushdown automaton is
of one of the following two types.  In the first type, an input symbol
is used.  Depending on the input symbol, the top symbol on each of the
2 stacks and the state of the finite control, the automaton moves to
a new state, the input head is moved to the right, and a (possibly
empty) string of symbols is pushed on each stack to replace the top
stack symbol of each stack.  The second type of transition is similar
to the first, except that the input symbol is not used and the input
head is not advanced. If the 2-stack pushdown automaton is
deterministic, exactly one transition is possible from any
configuration of the automaton, whereas if it is nondeterministic,
many transitions may be possible.

\item
The {\em MacDonalds Restaurant Placement Problem} is as follows. 
Given a list of $m$ malls and the distance between each pair,
is there a way to place a MacDonalds restaurant in each of at most 
$k$ malls, so that no mall is more than distance $d$ from
some restaurant?

The input consists of 
\begin{itemize}
\item a list of the malls $s_1,s_2,\ldots, s_m$,
\item a list of the distances between each pair, 
$d_{12}, d_{13}, \ldots , d_{1m}, d_{23}, \ldots, d_{m-1,m}$, where
$d_{ij}$ is the distance between malls $s_i$ and $s_j$,
\item a distance bound $d$ (such that all malls are to be
within distance $d$ from a restaurant) and
\item a restaurant bound $k$ (such that there are to be no more than
$k$ restaurants.
\end{itemize}

Show that the MacDonalds Restaurant Placement Problem is NP-complete.

(Hint: Give a polynomial time reduction from the Vertex Cover problem to
the MacDonalds Restaurant Placement Problem; consider the special case where $d=1$.)

\item
Suppose we want to give change to a customer using the smallest
number of coins in a particular currency. We are given a finite list
of the values of each coin in the currency, say $c_1, c_2, \ldots , c_n$,
where $c_1 < c_2 < \ldots < c_n$.  We are also given a target $T$, which is
the amount of change the customer needs.  We wish to compute a number,
{\sl COUNT}, which is the minimum number of coins in the currency needed to
make up the change. (Suppose for simplicity that there is always a
coin in the list worth exactly one unit of change, so that it is
always possible to construct the exact change for the customer).

a) Show that the following greedy algorithm does not always return the
correct {\sl COUNT}.

\begin{tabbing}
xxxxx\=xxx\= \kill
\>   Algorithm {\sl GREEDY}: input $T, c_1, c_2, ... , c_n$ \\
  
\>   {\sl SUM} $\leftarrow 0$ \\
\>   {\sl COUNT} $\leftarrow 0$ \\
\>   while {\sl SUM} $< T$ do \\
\>\>    let $c_i$ be the largest currency value such that \\
\>\>    {\sl SUM} + $c_i \le T$ but {\sl SUM} $+ c_{i+1} > T$ \\
\>\>    ( define $c_{n+1} = +\infty$ ) \\
\>\>    {\sl SUM} $\leftarrow$ {\sl SUM} $+ c_i$ \\
\>\>    endwhile \\
\>   output({\sl COUNT}).
\end{tabbing}

b) Using dynamic programming, construct an algorithm that correctly
computes {\sl COUNT} in time polynomial in $n$ and $T$.  What is the
running time of your algorithm?

\item
   In a permutation of the numbers $1, \ldots ,n$, a {\sl record} is a number that
   is larger than all of its predecessors.  For example, the permutation 

\begin{center}
		2, 3, 4, 1
\end{center}
   contains 3 records.

   Let $E_n$ denote the expected number of records in a random
permutation of $\{1, \ldots ,n\}$.

   Find a recurrence relation for $E_n$, and use it to estimate $E_n$
for large $n$.

\item
   Show that the set of powers of 4, written in base 8, is regular.
Generalize this to powers of $b^i$ written in base $b^j$.

\item
   Recall that the ``quicksort'' algorithm sorts a list $A[1], \ldots ,A[n]$
   as follows.  We choose an element $x$ from the list, separate the 
   remaining items into elements less than $x$ and elements greater than $x$,
   and recursively sort the smaller lists.

   Suppose we modify this algorithm as follows.  We choose two elements
   $x$ and $y$ from the list; suppose that $x<y$.  Next we separate the
   remaining elements into three sublists: elements less than $x$, elements
   between $x$ and $y$, and elements greater than $y$.  This gives three
   smaller lists, which are sorted recursively.

   a) In the fortunate case where equal splits occur, that is,
   the three sublists always have equal
   size, how many comparisons are done by the modified algorithm?

   b) Compare the modified algorithm with the original method.  Which
   uses the smaller number of comparisons?  (For simplicity, you can
   assume that in both methods, equal splits occur.)

\end{enumerate}

\end{document}