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

\head{1390}{Algorithms}{Winter 2001}{9 February 2001}{13}

\begin{center}
\Large{{\bf Sample midterm}} 
\end{center}

\begin{itemize}
\item 
This is a 60 minute midterm. It has three problems worth a total of
  200 points, and a bonus problem worth 20 points.
\item 
This is a closed-book exam.  You may only refer to your crib-sheet,
which is a single $8\frac{1}{2}\times 11$ sheet (with writing on both
sides) of notes.
\item
Show your work, as partial credit will be given.
\end{itemize}

\medskip

{\bf 1. (4 $\times$ 20 = 80 points) } Give a short answer to each of
the following questions.  
\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.

\[ \lg n \hs (\lg \lg n)^2 \hs \sqrt{n} \]

\item[{\bf (b)}] 
True or false: The height of any binary tree with $n$ nodes is
  $\Omega(\lg n)$.  Justify your answer.

\item[{\bf (c)}] 
A {\em max-heap\/} is a heap in which the value stored at every node
is less than the value stored at the parent of the node.  Is it true
that the minimum element in a max-heap is always stored at a leaf
node?  Briefly justify your answer. (Assume that all the keys in the
heap are distinct.)

\item[{\bf (d)}] 
Consider inserting the keys $10$, $22$, $31$, $59$, and $23$ into a
hash table of length $7$ using open addressing with the hash function
$f(k) = k \bmod 7$.  Illustrate the result of inserting these keys
using linear probing.
\end{itemize}

{\bf 2. (30 + 45 = 75 points)}
\begin{itemize}
\item[{\bf (a)}]
Solve the following recurrence relation.  Assume that $T(n)$ is $\Theta(1)$
for $n\le 2$.

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

\item[{\bf (b)}]
Consider the following implementation of Quicksort.

\begin{tabbing}
{\sc New-Quicksort}$(A,p,r)$ \hs (to sort $A[p..r]$)\\
1. \= If $p$ \= $< r$ \= then\\
2.\> \> Find the median $m$ of $A[p..r]$ using the linear-time selection algorithm
({\sc Select}).\\
3.\>\> Partition $A$ into two parts $A[p..q]$ and $A[q+1..r]$ such that every
element\\
\>\> in $A[p..q]$ is at most $m$ and every element in $A[q+1..r]$ is greater
than $m$.\\
4.\>\> {\sc New-Quicksort}$(A,p,q)$\\
5.\>\> {\sc New-Quicksort}$(A,q+1,r)$
\end{tabbing}
Argue that {\sc New-Quicksort} is a correct sorting algorithm.  Derive
and solve a recurrence for the worst-case running time of {\sc
New-Quicksort} on an array of $n$ elements.  Assume that all the
elements in the input array are distinct.
\end{itemize}

{\bf 3. (45 points)} 

A {\em mode}\/ of a list of elements is an element that appears in the
set most frequently.  For example, the list $\{2, 45, 53, 53, 2, 45,
53, 2, 81\}$ has two modes, $2$ and $53$, since each of them appears
more times than any other element in the set.

Design an efficient algorithm to determine a mode of a list of $n$ elements.
(If the list has more than one mode, then your algorithm may return any one of
the modes.)  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.

{\bf 4. (20 bonus points)} 

Design an $O(n k \lg k)$ time algorithm to merge $k$ sorted lists of
$n$ elements each into one sorted list of $nk$ elements.  Justify the
running time of your algorithm.
\end{document}

