\documentstyle[11pt]{article}
\begin{document}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{center}{\Large\bf FUNDAMENTAL ALGORITHMS MIDTERM}\end{center}
\begin{quote}
In five minutes you will say that it is all so absurdly simple.
\\ Sherlock Holmes, The Adventure of the Dancing Man
\\ Sir Arthur Conan Doyle
\end{quote}
\noindent No calculators, no notes. Do all problems. Maximal score: $125$.
\ben
\item (20) Let $A[1\cdots N]$ and $B[1\cdots N]$ be arrays of numbers that are
already in increasing order.
Give an efficient algorithm for creating an array $APPLE[1\cdots 2N]$ consisting
of the $2N$ entries in $A$ and $B$, placed in increasing order. How long
(give a short reason) does your algorithm take?
\item (20) For the following algorithms let $T(N)$ denote the total number of times the
step after the
{\tt WHILE} step is reached.
For the first
algorithm give an {\em exact} formula for $T(N)$. For the second algorithm first
give $T(N)$ as a precise sum. Then
find $T(N)$ is the form $T(N)=\Theta(g(N))$ for a standard $g(N)$.
Reasons please!
\ben
\item
W=1
\\ WHILE W $<$ N
\\ \hsa do W=2*W
\\ END WHILE
\item
FOR J=1 TO N
\\ \hsa V=J
\\ \hsa WHILE $V \leq N$
\\ \hsb do V=2*V
\\ \hsa END WHILE
\\ END FOR
\een
\item (20) Let $W[1\cdots N]$ be an array of integers with all $1\leq W[i] \leq K$.
Give (psuedocode is fine) the algorithm {\tt COUNTINGSORT} that ends with
$W$ in increasing order. (You may, and should, create auxilliary arrays.)
Analyze the running time of {\tt COUNTINGSORT} when $K=N$. (Note: It is not
sufficient simply to give the answer, an analysis is called for.)
\item (25) Consider the following Binary Search Tree {\tt TREE} with {\tt ROOT(TREE)=R}.
(The values have been deliberately excluded. Assume the values are distinct.))
\begin{center}
\begin{tabular}{rrrrrrrrrr}
vertex & A & G & H & I & L & M & O & R & T\\
leftchild & NIL & L & T & NIL & NIL & NIL & NIL & A & NIL \\
rightchild & G & O & M & H & NIL & NIL & NIL & I & NIL \\
parent & R & A & I & R & G & H & G & NIL & H
\end{tabular}
\end{center}
\ben
\item (5) Draw a (nice!) picture of this tree.
\item (10) Which is the vertex with minimal value. Illustrate how the
program {\tt MIN} will find it.
\item (10) Give the vertices of the tree in increasing order of value.
(Give an indication of your method, but you needn't give every detail.)
\een
\item (20) Let $A$ be an array of length $127$ in which the values are
distinct and in increasing order.
\ben
\item In the procedure
{\tt BUILD-MAX-HEAP(A)} {\em precisely} how many times will two elements
of the array be exchanged? (Reason, please!)
\item Now suppose the values are distinct and
in decreasing order. Again,
in the procedure
{\tt BUILD-MAX-HEAP(A)} {\em precisely} how many times will two elements
of the array be exchanged? (Reason, please!)
\een
\item (20) Consider an algorithm {\tt BOHOC} for multiplication of
two $n$ digit numbers. (Don't worry about how {\tt BOHOC} really
works, we just want an analysis based on the information below.)
It multiplies two $n$ digit numbers by making five recursive calls
to multiplication of two $n/2$ digit numbers plus two additions of
$n$ digit numbers. Each of the additions take
time $O(n)$. Give the recursion for the time $T(n)$ for {\tt BOHOC} and
use the Master Theorem to find the asymptotics of $T(n)$. Is {\tt BOHOC}
a good algorithm to use for $n$ large? Give brief reason for your answer.
\een
\begin{quote}
She had been born with a map of time in her mind. She
pictured other abstractions as well, numbers and the
letters of the alphabet, both in English and in Bengali.
Numbers and letters were like links on a chain. Months
were arrayed as if along an orbit in space.
\\ Jhumpa Lahiri, The Lowland
\end{quote}
\end{document}