\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}{10 February 1999}{15}


\begin{center}
\Large{\bf Quick Solutions to 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)$.

{\bf Answer:} False.  $2^n \neq \Omega(3^n)$ since $2^n/3^n = 1/(1.5)^n$ tends
to zero as $n$ tends to infinity.

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

{\bf Answer:} False.  The best-case running time of binary search is
$\Theta(1)$ since if you may find the element of interest in a single step if
you are lucky.

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

{\bf Answer:} True.  Let the average be $x$ and the median be $y$.  Then $xn$,
which is the total sum of all the numbers is at least the sum of the $(n
+ 1)/2$ highest numbers, each of which is at least $y$.  Therefore $nx \ge
(n+1)y/2$, which implies that $x \ge y/2$.

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

{\bf Answer:} Not true.  Take $f(n) = 2^n$.  We get $f(n/2) = 2^{n/2}$.  Now
$2^{n/2} \neq \Omega(2^n)$ since $2^{n/2}/2^n = 1/2^{n/2}$ tends to zero as
$n$ tends to infinity.
\end{itemize}

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

{\bf Answer:} Use the Master method.  Set $a = 11$, $b = 10$, and $f(n) =
n/\log n$.  We get $n^{\log_b a} = n^{\log_{10}(11)} \approx n^{1.04}$.  If we
set $\eps = .04$, then we get $n/\log n = O(n) = O(n^{1.04 - \eps})$.
Therefore, case~1 applies.  We get $T(n) = \Theta(n^{\log_{10}11})$.
\item[(b)]
$T(n) = T(n/2) + T(n/4) + n^2$.

{\bf Answer:} We use the recursion tree method.  In the first level, we get
$n^2$.  In the second level, we get $n^2/4 + n^2/16 = 5n^2/16$.  In the next
level, we get $n^2/16 + n^2/64 + n^2/64 + n^2/256 = 25n^2/256 = (5/16)^2n^2$.
Thus, we get a converging sum $n^2(1 + 5/16 + (5/16)^2 + \ldots) \le n^2/(1 -
5/16) = O(n^2)$.  The lower bound $T(n) = \Omega(n^2)$ follows directly from
the recurrence statement.
\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 Answer:} If $n$ is even, we can write $a^n = (a^{n/2})^2$.  If $n$ is
odd, we can write $a \times (a^{\lfloor n/2\rfloor})^2$.  Thus, we can reduce
a problem of size $n$ to a problem of size $\lfloor n/2 \rfloor$ and then at
most 2 additional multiplications.  Therefore $T(n) \le T(\lfloor n/2 \rfloor)
+ 2$, and we get $T(n) = O(\lg n)$.

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

{\bf Answer:} The recurrence we get is the following: $T(n) = 3T(2n/3) +
\Theta(1)$.  We can use the master method.  Since $f(n) = \Theta(1)$ and
$n^{\log_b a} = n^{\log_{3/2} 3}$, we get case~1.  Therefore, $T(n) =
\Theta(n^{\log_{3/2} 3})$.  Since $\log_{3/2} 3 > 2$, {\sc Stooge-Sort} is
worse than all of the algorithms we have covered in class.
\end{document}