\documentstyle[12pt,handout]{article}
\begin{document}
\input{epsf}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{courseMacros}

\newcommand{\heapsize}{\mbox{{\em heap-size}}}
\newcommand{\len}{\mbox{{\em length}}}
\newcommand{\power}{\mbox{{\sc Power}}}

\newcommand{\ins}{\mbox{{\sc Insert}}}
\newcommand{\del}{\mbox{{\sc Delete}}}
\newcommand{\search}{\mbox{{\sc Search}}}
\newcommand{\mini}{\mbox{{\sc Minimum}}}
\newcommand{\maxi}{\mbox{{\sc Maximum}}}
\newcommand{\suc}{\mbox{{\sc Successor}}}
\newcommand{\pred}{\mbox{{\sc Predecessor}}}
\newcommand{\subtreemin}{\mbox{{\sc SubtreeMin}}}
\newcommand{\rt}{\mbox{{\it root}}}

\head{1390}{Algorithms}{Winter 2001}{15 February 2001}{15}

\begin{center}
\Large{{\bf Midterm}} 
\end{center}

{\bf Instructions.}
\begin{itemize}
\item This is a 60 minute midterm. It has four problems worth a total
  of 200 points, and a bonus problem worth 20 points.

\item
Read all the problems through first and attack them in the order that allows
you to make the most progress.

\item While describing an algorithm, you may use any of the algorithms
  covered in class or in the text as a subroutine.  You need to
  provide a proof of correctness and/or an analysis of the running
  time only for those problems where they are explicitly required.

\item
Show your work, as partial credit will be given.  If you need extra space, use
the blank facing page.  

\item
Best of luck!
\end{itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 45 \\ \hline
2 & & 35 \\ \hline
3 & & 80 \\ \hline
4 & & 40 \\ \hline
Bonus & & 20 \\ \hline
Total & & 200 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill


\newpage

{\bf Problem 1.  (3 $\times$ 15 = 45 points) \hs} 
\begin{itemize}
\item[{\bf (a)}] 
Arrange the following functions in order from the slowest growing
  function to the fastest growing function.  You may simply state the
  answer without any additional justification.

\[ \log^2 n   \hs \hs 2^{\sqrt{n}} \hs \hs 100n^3 \]	

\vfill 

\item[{\bf (b)}]
Indicate, with a brief justification, whether the following statement
is true:  The following recurrence relation can be solved by the
Master theorem.
\[T(n) = 2T(n/2) + n\lg n\]


\vfill

\item[{\bf (c)}] 
Indicate, with a brief justification, whether the following statement
is true:  The average of any set of $n$ numbers is always at least
half the median.  (You may assume that $n$ is odd.)  

\vfill
\end{itemize}

\newpage

{\bf Problem 2. (35 points) \hs} Derive a tight bound for the
following recurrence relation.  Assume that $T(n)$ is $\Theta(1)$ for
$n\le 4$.

\[ T(n) = 2T(n/4) + T(n/2) + n.\]


\newpage
{\bf Problem 2. (30 + 50 = 80 points) \hs} Consider the following algorithm for
calculating the $n$th power of a number $a$.

\begin{tabbing}
$\power(a, n)$\\
1. \= \algif\ \= $n = 0$\\
2. \> \> return 1\\
3. \> \algelse \\
4. \> \> return $a \times \power(a, n-1)$
\end{tabbing}

\begin{itemize}
\item[{\bf (a)}] Write a recurrence relation for the number of
multiplications performed by $\power$.  Solve the recurrence.

\vfill

\item[{\bf (b)}] Describe a faster algorithm for the problem that
performs $O(\lg n)$ multiplications.  Justify the upper bound on the
number of multiplications performed by your algorithm.  ({\em Hint:}
Think divide-and-conquer.)

\vfill
\end{itemize}
\newpage

{\bf Problem 4. (40 points) \hs} You and your valentine each have a
long list of favorite restaurants.  On Valentine's Day, each of you
wants to go to a restaurant of your own liking.  Design an efficient
algorithm to determine whether there exists a restaurant that you both
like.  Assume that each list is of size $n$.  Analyze the worst-case
running-time of your algorithm.  The more efficient your algorithm is
in terms of its worst-case running time, the more credit you will get.

\newpage

{\bf Bonus Problem (20 bonus points) \hs} The $k$th {\em quantiles}\/
of an $n$-element set are the $k-1$ elements of the set that divide
the sorted set into $k$ equal-sized sets (assume that $n$ is a
multiple of $k$).  Give an $O(n \lg k)$-time algorithm to list the
$k$th quantiles of a set.  You may assume that all the elements of the
set are distinct.

\end{document}

