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

\head{1390}{Algorithms}{Winter 2000}{10 February 2000}{10}

\begin{center}
\Large{\bf Practice Problems for Midterm}
\end{center}

{\bf 1.} For each of the following statements, indicate whether it is true or
false.  Briefly justify your answers.

\begin{itemize}
\item[{\bf (a)}] $n^{\lg n} = O((\lg n)^n)$.

\item[{\bf (b)}] For every monotonically increasing positive function $f(n/2) = \Omega(f(n))$.
  
\item[{\bf (c)}] The fifth largest element in a heap can be determined
  in $O(1)$ time.
  
\item[{\bf (d)}] The height of any binary tree with $n$ nodes is
  $\Omega(\lg n)$.
\end{itemize}

{\bf 2.} Solve the following recurrences.  In each case, you may
assume that $T(n)$ is constant for $n \le 10$.
\begin{itemize}
\item[(a)]
$T(n) = 11\cdot T(n/10) +n$.

\item[(b)]
$T(n) = T(n/2) + T(n/4) + n^2$.
\end{itemize}

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

{\bf 4.} 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.
\end{document}