\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/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 1999}{9 February 1999}{14}


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

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

\begin{itemize}
\item[(a)] $2^n = \Theta(3^n)$.

\item[(b)] The best-case running time of binary search is $\Omega(\lg n)$.

\item[(c)] The average of a set of $n$ numbers is always at least half the
median.  (Assume that $n$ is odd.)

\item[(d)] For every monotonically increasing positive function $f(n/2) = \Omega(f(n))$.

\end{itemize}

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

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

{\bf 3.} Suppose we are given positive integers $a$ and $n$ and asked to
compute $a^n$, that is, the $n$th power of $a$.  The simplest algorithm
performs $n - 1$ multiplications by computing $a \times a \times
\ldots \times a$.  Design a divide-and-conquer algorithm that computes $a^n$
using $O(\lg n)$ multiplications.  Justify the running time of the algorithm.

{\bf 4.} Parts~(b) and~(c) of Problem~8--3.
\end{document}