%Date:     Mon, 22 Jan 96 8:40:45 EST from    Kishan Mehrotra   <kishan@top>
\documentstyle[12pt,eepic,epic]{article}
\setlength{\textheight}{8.625in}
\setlength{\topmargin}{-1cm}
\setlength{\oddsidemargin}{+1mm}
\setlength{\textwidth}{6.5in}
\newcommand{\lra}{\rightarrow}
\newcommand{\Llra}{\Longleftrightarrow}
\newcommand{\Lra}{\Longrightarrow}
\newcommand{\Lla}{\Longleftarrow}
\newcommand{\lla}{\leftarrow}
\newcommand{\ov}{\overline}
\newcommand{\mc}{\multicolumn}
\newcommand{\qed}{{\hfill$\Box$}}
\newcommand{\bm}{\boldmath}
\renewcommand{\baselinestretch}{1.5}
%\pagestyle{empty}

\begin{document}

\begin{center}{\large\bf Analysis of Algorithms\\ \medskip
 January, 1996 } \end{center}
{\bf Note:\quad  Answer all questions. Each problem carries 
equal points.}  You must write your Social Security
number on each answer book. {\bf Do not} write your name.

\bigskip


\begin{enumerate}
\item Is it possible to use the  ``binary search'' 
technique to devise an algorithm for the
problem of finding $\left\lceil\sqrt{N}\right\rceil$ of a positive
integer $N$? If yes, explain why your algorithm is binary 
and analyze its performance in
detail. (Do not write the code---express the algorithm in words.)

\item  \begin{enumerate}
\item Prove that it is not possible to find the best (largest of an
array of $n$ elements) in less than $n-1$ comparisons. 
\item What is wrong with the following argument?
\begin{quote}
We have shown that $n-1$ comparisons are necessary 
to find the best. By symmetry, $n-1$ comparisons are necessary 
to find the worst. 
Therefore $2n-2$ comparisons are necessary
to find the best and the worst.
\end{quote}
\end{enumerate}

\item We know that one can build $T_n = {2n \choose n}/(n+1)$ binary
search trees with $n$ nodes. [$T_n$ is also known as the Catalan number
and randomly built binary trees, with equal probability $T_n^{-1}$
are called the Catalan trees.] Show that
\begin{enumerate}
\item Probability that in a randomly built Catalan tree with $n$ nodes
the left subtree has $k$ nodes is given by  
$$\frac{T_k T_{n-k-1}}{T_n}.$$
\item Let $Q_n$ denote the average internal path length of the Catalan
trees with $n$ nodes. Show that 
\begin{eqnarray*}
Q_0 & = & 0\\
Q_n & = & (n-1) + \sum_{1\leq k \leq n} \frac{T_{k-1} T_{n-k}}{T_n}
(Q_{k-1} + Q_{n-k}) \mbox{ for } n > 0
\end{eqnarray*}
\end{enumerate}

\item  Let $x[1..n]$ be an array of integers in an arbitrary order, and
let $a[1..n]$ be another array of distinct integers from 1 to $n$
(namely $a[1], \ldots, a[n]$ is a {\em permutation} of 1, 2, $\ldots, n$). 
Design an $O(n\log n)$ algorithm to order the first sequence 
according to the order imposed by the permutation. 
In other words, for each $i$, $x[i]$ should appear in the position given
in $a[i]$. For example, if $x = 17, 5, 1, 9$, and $a = 3, 2, 4, 1$
then the outcome should be $x = 9, 5, 17, 1$.
\item 
\begin{enumerate}
\item  Show that the single-source shortest path constructed by the 
Dijkstra's algorithm on a connected undirected graph forms a spanning
tree. 
\item Is the spanning tree form by Dijkstra's algorithm on a connected
undirected graph a min-cost spanning tree?
\end{enumerate}


\end{enumerate}

\end{document}
