\documentstyle[12pt,handout]{article}
\begin{document}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}

\head{1390}{Algorithms}{Winter 1999}{11 February 1999}{16}

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

{\bf Instructions.}
\begin{Itemize}
\item
This is a 60 minute midterm. It has three problems worth a total of 200 points
and one bonus problem worth 40 points.

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

\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 & & 80 \\ \hline
2 & & 70 \\ \hline
3 & & 50 \\ \hline
Bonus& & 40 \\ \hline
Total & & 200 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

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


\newpage

{\bf 1.  (4 $\times$ 20 = 80 points)} 

Give a short answer to each of the following questions.  Briefly justify your
answers.
\begin{itemize}
\item[{\bf (a)}]
Is $\log^2 n = \Omega(n)$?

\vfill

\item[{\bf (b)}]
Is $f(n^2) = O((f(n))^2)$ true for all functions $f(n)$ that are positive and
monotonically increasing?

\vfill

\item[{\bf (c)}] We know that the largest element in a heap $A$ of $n$
distinct elements is $A[1]$ and, hence, can be determined in $O(1)$ time.  Can
the second largest element in a heap be determined in $O(1)$ time?  \vfill
\newpage

\item[{\bf (d)}] Is the following statement true?  If the worst-case running
time of an algorithm $A$ is $\Theta(n)$, then there exist positive constants
$c_1$, $c_2$, and $n_0$, such that the running time of $A$ on every input of
size $n$ is at least $c_1 n$ and at most $c_2 n$ for all $n \ge n_0$.

\vfill
\end{itemize}

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

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

\vfill

\newpage

\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}

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}

\newpage

{\bf 3. (50 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.

\newpage

{\bf 4. (40 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}

