\documentstyle[draft,defs,12pt]{article}
\renewcommand{\baselinestretch}{1.10}
\topmargin 0pt
\textheight 22cm
\hfuzz=6pt
\pagestyle{empty}
\input{eepic.sty}
\input{macs}
\newcommand{\quiz}{1}
\newcommand{\lla}{\longleftarrow}
\newcommand{\duedate}{Thursday, April 21}
%\newdefinition{\problem}{Problem}
\thispagestyle{empty}
\begin{document}
\mbox{}
%\vspace{.25in}
\begin{center}{\Large \bf Comprehensive Examination \\ \bigskip
 Design and Analysis of Algorithms}\\ \bigskip
{\large \bf  February 11, 1995}
\end{center}

{\bf Note:\quad  Answer all questions. Points assigned to each problem are
indicated after the problem.}  You must write your Social Security 
number on each answer book. {\bf Do not} write your name.

\begin{enumerate}
\item  An interesting sequence of trees is the binomial trees (note that
these are just plain trees---not binary, not extended) defined by
\begin{figure}[hbt]
\centering
\input{comp1.tex}
\end{figure}

\noindent and, in general,

\begin{figure}[hbt]
\centering
\input{comp2.tex}
\end{figure}
\begin{enumerate}
\item Show that $B_m$ has $2^m$ nodes.\hfill [2 points]
\item Prove that the number of nodes in $B_m$ at level $k$ is the binomial
coefficient $m\choose k$. Recall that the level of a node is 0,  if it is
the root node and (1 + the level of the parent node), otherwise.\hfill [3 points]
\item We naturally define the path length of a tree to be the sum of the
levels of all its nodes (just one kind of node here, with no division
into
external or internal). Let $P_m$ be the path length of $B_m$. State a
recurrence relation defining $P_m$ and find the solution in closed form.
\hfill [5 points]
\end{enumerate}

\item In an array of $n$ distinct elements $A[1],\ldots,A[n]$, the rank of
$A[i]=\ell, 1\le \ell\le n$ if exactly  $(\ell-1)$ of the $A[j]$'s are
less than $A[i]$, i.e.,
$$\sum^n_{j=1}\ I_{(A[j] \le A[i])}=\ell$$
where
$$I_{(A[j]\le A[i])}=\left\{ \begin{array}{ll}
1 \ \mbox{ if }&A[j]\le A[i]\\
0&\mbox{otherwise}.\end{array}\right.$$
In particular, three quartiles of an array of $n$ elements, denoted by
$Q_1,Q_2,$ and $Q_3$, are elements with ranks $\lceil n/4\rceil,\lceil
n/2\rceil$, and $\lceil 3n/4\rceil$, respectively.

Give an $O(n)$-time algorithm to find the three quartiles of an array
of size $n;n\ge 4$. Explain why your (suggested) algorithm is of the specified
order.\hfill [6 points]

\item The partitioning problem is:
\begin{quote}
Given $n$ integers, is there a way to partition the integers into two
disjoint subsets so that the sums of the integers in each of the two
subsets are equal? Formally, given $x_1,\ldots,x_n$, is there a subset $I$
of $\{1,2,\ldots,n\}$ such that
$$\sum_{i\in I}\ x_i=\sum_{i\notin I}\ x_i?$$
\end{quote}
Give a dynamic programming algorithm for this partitioning problem. Estimate
the running time of your algorithm.\hfill [15 points]
\item  Let $T$ be a minimum spanning tree of a graph $G=(V,E)$. 
Let $V'$
be a subset of $V$, $T'$ be the subgraph of $T$ induced by $V'$,
and $G'$ be the subgraph of $G$ induced by $V'$. Show that if $T'$
is connected, then $T'$ is a minimum spanning tree of $G'$.\hfill [5
points]
\item You wish to prove that a problem, $PROB$, is NP-complete. What are the
key steps to prove ``$PROB$ is NP-complete'' and why? Give appropriate
details.\hfill [8 points]
\item  Consider the sorting problem of a very large number of keys that
cannot be put into the active memory all at one time. Let $n$ denote the
number of keys to be sorted and $m$ be the number that can be sorted in
active memory. Let $T_0$ denote the tape which contains all data, all $n$
of them, and $T_1,T_2,T_3$ are three additional tapes (a tape is an
external memory device). The following algorithm describes a sorting
procedure.

%\pagebreak

\begin{quote}
Phase I. [Run construction and distribution]\\
\mbox{\hspace{1em}}{\bf while} there are more records on $T_0$ {\bf do}
\begin{description}
\begin{description}
\item [1.] Read $m$ records (perhaps less the last time)
\item [2.]Sort them using an internal sorting algorithm.
\item [3.]If the previous run (a sorted set of $m$) was put on $T_2$, then
put this on $T_3$; else on $T_2$.
\end{description}
\end{description}
\mbox{\hspace{1em}}{\bf end}\\
\mbox{\hspace{3em}}Rewind the tapes.\\
Phase II. [Merging the runs]\\
\mbox{\hspace{3em}}$i_1,\lla2,i_2\lla3$ [indexes of input tapes]\\
\mbox{\hspace{3em}}$j_1,\lla0,j_2\lla1$ [indexes of output tapes]\\
\mbox{\hspace{1em}}{\bf while} there is more than one run {\bf do}
\begin{description}
\begin{description}
\item [1.] Merge the first run on $T_{i1}$ with the first run on $T_{i2}$
and put the result on $T_{j1}$.
\item [2.] Merge the next run on $T_{i1}$ with the next run on $T_{i2}$
and put the result on $T_{j2}$.
\item [3.] Repeat steps 1 and 2 (putting the output alternately on $T_{j1}$
and $T_{i2}$) until the end of the data on $T_{i1}$ and $T_{i2}$.
\item [4.] Rewind the tapes. Add 2 (modulo 4) to $i_1,i_2,j_1$, and  $j_2$ and
repeat steps 1, 2, 3 until done.
\end{description}
\end{description}
\end{quote}

\begin{enumerate}
\item  For $n=25$ and $m=4$, show how this algorithm will proceed to sort

20, 3, 25, 11, 17, 4, 6, 5, 18, 2, 21, 12, 19, 1, 7, 14, 15, 9, 8, 13, 10,
23, 22, 24, 16. \hfill [3 points]

\item Analyze this algorithm, i.e., find the running time of this
algorithm (in closed form) for $n,m \geq 4$. Make appropriate assumptions.
\hfill [8 points]
\end{enumerate}
\item Let $\omega_1$ and $\omega_2$ be, respectively, primitive $m$-th 
and $n$-th
roots of unity. The {\it two-dimensional discrete Fourier Transform} of a
matrix\\ $a[0..m-1,0..n-1]$ is a matrix $v[0..m-1,0..n-1]$ defined as
\begin{equation}
v_{k,\ell}=\sum^{m-1}_{i=0}\ \sum^{n-1}_{j=0}\ a_{i,j}x^i_ky^j_\ell,
\end{equation}
where, for $k=0,1,\ldots,m-1,x_k=\omega^k_1$, and, for
$\ell=0,1,\ldots,n-1,y_\ell=\omega^\ell_2$.
\begin{enumerate}
\item How much time does it take to compute the array $v$ directly from
(1)?\hfill [5 points]
\item Show that $v$ can be computed in $O(mn \log\, (mn))$ time using the FFT.
Assume both $m$ and $n$ are powers of 2.\hfill [10 points]
\end{enumerate}
\end{enumerate}
\end{document}
