\documentstyle[11pt]{article}
\begin{document}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\noi}{\noindent}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\newcommand{\Co}{\\ {\tt Comment:}}
\begin{center}{\Large\bf FUNDAMENTAL ALGORITHMS\\ PRACTICE MIDTERM}\end{center}
\ben
\item (35) These questions concern a max-heap $A$ with auxilliary
structures {\tt heapsize[A]}, {\tt Left[i]}, {\tt Right[i]} and
{\tt Parent[i]}.
\ben
\item (5) Give the max-heap property. (That is, what is the
relationship between the values $A[i]$ that one needs for a
heap.)
\item (5) Suppose {\tt length[A]}=110 and the values $A[i]$ are
distinct. What are the possible $i$ for which $A[i]$ is
the second largest value? (You must give all possible $i$.)
\item (5) Suppose {\tt length[A]}=110 and the values $A[i]$ are
distinct. What are the possible $i$ for which $A[i]$ is
the smallest value? (You must give all possible $i$.)
\Co $i$ must be a leaf, that is, have no children.
Some noted the last row went from $64$ to $110$ but there
were some on the row above that that had no children. As the
left child of $i$ would be $2i$ the condition is that $2i > 110$,
or $i \geq 56$.
\item (10) Describe the algorithm {\tt MAX-HEAP-INSERT(A,key)}
which adds to heap $A$ a new entry with value {\tt key}.
(Either a description in words or a pseudocode program
would be fine.)
\item (10) How long (in worst case) does the above algorithm
take as a function of $n=${\tt length[A]}?
Give a {\em reason} for your answer.
\een
\item (25) Write the expressions below as $\Theta(g(n))$
where $g(n)$ is of one of the forms $n^a$, $\ln^bn$, $n^a\ln^bn$.
For the second and third parts give a short argument for your answer.
\ben
\item (5) $10n\lg n + 89 + 3n^2$
\item (10) $\sqrt{1}+\sqrt{2}+\ldots+\sqrt{n-1}+\sqrt{n}$
\item (10) The average time {\tt QUICKSORT} takes to sort
an array of (caution: curve ball!) size $n^4$.
\een
\item (10) Consider the following fragment of a program:
\\ \hsa J=I
\\ \hsa WHILE J $\leq$ N
\\ \hsb do J=2*J
\\
Give a precise formula for the number of times the third step
is applied. Your answer will be a function of $I$ and $N$.
(Nearly full credit if you are off by one.)
\item (15)
Consider the following program:
\\ X=0
\\ FOR I=1 to N
\\ \hsa K=1
\\ \hsa WHILE I*K $\leq$ N
\\ \hsb K ++
\\ Analyze the time this program takes as an asymptotic function
of $N$. [Nearly full credit was given for expressing the time as a sum
as the sum had not been examined in class.]
\item (25) These questions concern {\tt BUCKET-SORT}. We assume that
the input in an array $A[1\cdots n]$ with all $0\leq A[i]< 1$.
We will assume an auxilliary array $B[0\ldots (n-1)]$ of linked
lists, or buckets. We assume an algorithm $SORT[C]$ which will
sort a linked list $C$. This will be a black box that we will
apply to the linked lists $B[i]$.
\ben
\item (10) Give the algorithm for {\tt BUCKET-SORT[A]}.
\item (5) What side assumption do we make, under which {\tt BUCKET-SORT}
is an excellent algorithm.
\item (10) Assume $SORT[C]$ takes time $m^2$ when $C$ is a list of
length $m$. Now assume that the data $A[i]$ are actually uniformly
distributed between $0$ and $n^{-1/2}$. How long will
{\tt BUCKET-SORT[A]} take.
\een
\item (20) Consider the recursion
\[ T(n) = 2T(n/2) + 3n \]
with initial condition $T(1)=0$. We shall {\em assume}
$n$ is a power of two.
\ben \item (5) What is $T(8)$ precisely.
\item (5) What does the Master Theorem tell you about the
asymptotic growth of $T(n)$?
\item (5) Making the substitution $S(n)=T(n)$ create a recursion
for $S(n)$.
\item (5) Solve the recursion for $S(n)$ precisely. Using this,
give the precise value for $T(n)$.
\een
\een
\end{document}