\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}\\ SOLUTIONS \end{center}
\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?
\So This is the MERGE algorithm. The time is $O(N)$.
\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
\So When you hit the WHILE for the $t$-th time $W=2^{t-1}$. So you want the
maximal $t$ so that $2^{t-1}< N$, or $2^{t-1}\leq N-1$ or $t \leq 1 + \lg(N-1)$
so $\lfloor 1+\lg(N-1) \rfloor$.
\item
FOR J=1 TO N
\\ \hsa V=J
\\ \hsa WHILE $V \leq N$
\\ \hsb do V=2*V
\\ \hsa END WHILE
\\ END FOR
\So The inner loop takes (ignoring floors and ceilings) $\lg(N/J)$ so you want
$\sum_{J=1}^N \lg(N/J)$. One approach is that this is $\lg(N^N/N!)$. But by
Stirling's Formula $N^N/N! \sim e^N (2\pi N)^{-1/2}$ so the $\lg$ is $\Theta(N)$.
\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.)
\So This is basic COUNTINGSORT. When $K=N$ all three parts take time $O(N)$
for a total time of $O(N)$.
\een
\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.
\So Start at the root with R and children A,I. Continuing
\begin{verbatim}
R
A I
G H
L O T M
\end{verbatim}
\item (10) Which is the vertex with minimal value. Illustrate how the
program {\tt MIN} will find it.
\So Start at root R. Go to left A. Go to left NIL. So A is the MIN.
\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.)
\So IOTW(R) calls IOTW(A). Nothing on left so print A. Now call
IOTW(G). Left to L, print L; print G; then print O; finish IOTW(G);
finish IOTW(A); print R; Now IOTW(I). Final answer: ALGORIITHM
\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!)
\So (from first assignment!)
BUILD-MAX-HEAP(A) starts from I = LENGTH(A)/2 DOWN to 1, every I will
do Max-Heapify. \\ For $32\leq I\leq 63$ ,there should be one exchange.
\\ For $16\leq I \leq 31$, there should be 2 exchanges.
\\ For $8\leq I \leq 17$, there should be 3 exchanges.
\\ For $I=4,5,6,7$ , there should be 4 exchanges.
\\ For $I = 2,3$ there should be 5 exchanges.
\\ The root goes down to the bottom, 6 exchanges.
\\ Total: $32\cdot 1+16\cdot 2+8\cdot 3+4\cdot 4+2\cdot 5+1\cdot 6 = 120$
\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!)
\So Never! Each element will be placed originally in precisely its
correct final spot.
\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.
\So $T(n)=5T(n/2) + O(n)$. This is the low overhead case so $T(n) = \Theta(n^{\alpha})$
wth $\alpha = \log_25$. As $\log_25 > 2$ this is taking more than time $O(n^2)$
which is what the standard multiplication takes so, no, this is not a good algorithm.
\een
\end{document}