\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/W00/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 2000}{27 January 2000}{7}

\begin{center}
\Large{\bf Sample Solution to Problem Set 1}
\end{center}

\bigskip

{\bf 1. (8 points)} We have seen the following bound in class.
\[\sum_{1 \le i \le n} i^2 = \Theta(n^3).\]
Derive an asymptotically tight bound on the summation 
\[\sum_{1 \le i\le n} i^c,\]
where $c \ge 0$ is a given constant real number.

{\bf Answer:} We use the connection between summations and
integration.  For the upper bound, we have
\begin{eqnarray*}
\sum_{1 \le i \le n} i^c & \le & \int_1^{n+1} i^c di\\
& = & \frac{(n+1)^{c+1} - 1}{c + 1}\\
& \le & \frac{2^{c+1} n^{c + 1}}{c + 1}.
\end{eqnarray*}
Since $2^{c+1}/(c + 1)$ is a constant, we obtain that $\sum_{1 \le i
  \le n} i^c$ is $O(n^{c + 1})$.

For the lower bound, we have
\begin{eqnarray*}
\sum_{1 \le i \le n} i^c & \ge & \int_0^{n} i^c di\\
& = & \frac{(n)^{c+1}}{c + 1}.
\end{eqnarray*}
which implies that $\sum_{1 \le i \le n} i^c$ is $\Omega(n^{c + 1})$.

{\bf 2. (12 points)} Arrange the following functions in order from the
slowest growing function to the fastest growing function.  Briefly
justify your answer.  ({\em Hint:} It may help to plot the functions
and obtain an estimate of their relative growth rates.  It may also
help to express each function as a power of $2$ and then compare.)

\[ 
n^{3/2} \hs 100(\lg n)^2 \hs n\lg n \hs 2^{n/3} + n^{1.1}
\]

{\bf Answer:} The order from slowest growing to the fastest growing
function is: $100(\lg n)^2$, $n \lg n$, $n^{3/2}$, and $2^{n/3} +
n^{1.1}$.  We prove this using three steps: (i) $100(\lg n)^2 = o(n
\lg n)$, (ii) $n \lg n = o(n^{3/2})$, and (iii) $n^{3/2} = o(2^{n/3} +
n^{1.1})$.
\begin{itemize}
\item[(i)] We use the connection between asymptotic notation and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{100(\lg n)^2}{n \lg n} & = & 
\lim_{n \rightarrow \infty} \frac{2^{2\lg \lg n + \lg 100}}{2^{\lg n + \lg \lg n}}\\
& = & \lim_{n \rightarrow \infty} \frac{1}{2^{\lg n - \lg \lg n - \lg 100}}\\
& = & 0,
\end{eqnarray*}
since $\lg n - \lg \lg n - \lg 100$ goes to $\infty$ as $n$ goes to
$\infty$.  Therefore, $100 (\lg n)^2 = o(n \lg n)$.

\item[(ii)] We again use the connection between asymptotic notation and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{n\lg n}{n^{3/2}} & = & 
\lim_{n \rightarrow \infty} \frac{\lg n}{\sqrt{n}}\\
& = & \lim_{n \rightarrow \infty} \frac{2(\lg e) \sqrt{n}}{n}\\
& = & 0,
\end{eqnarray*}
where we use L'Hopital's rule in the penultimate step.  
Therefore, $n \lg n = o(n^{3/2})$.

\item[(iii)] We again use the connection between asymptotic notation
  and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{n^{3/2}}{2^{n/3} + n^{1.1}} & \le & 
\lim_{n \rightarrow \infty} \frac{2^{1.5\lg n}}{2^{n/3}}\\
& = & \lim_{n \rightarrow \infty} \frac{1}{2^{n/3 - 1.5\lg n}}\\
& = & 0,
\end{eqnarray*}
since $n/3 - 1.5\lg n$ goes to $\infty$ as $n$ goes to $\infty$.
Therefore, $n^{3/2} = o(2^{n/3} +n^{1.1})$.
\end{itemize}


{\bf 3. (3 $\times$ 6 = 18 points)} Let $f(n)$, $g(n)$, and $h(n)$ be
asymptotically positive and monotonically increasing functions.  Prove
or disprove each of the following conjectures.  For proving the
conjecture, you must show that the conjecture holds for all functions.
For disproving, you must show that there exists a setting of functions
for which the conjecture does not hold.
\begin{itemize}
\item[{\bf (a)}]
$f(n) + g(n) = \Theta(\max\{f(n), g(n)\})$.

{\bf Answer:} True.  This follows from the inequalities $f(n) + g(n)
\ge \max\{f(n), g(n)\}$ for all $n$ and $f(n) + g(n) \le 2\max\{f(n),
g(n)\}$ for all $n$.

\item[{\bf (b)}]
If $f(n) = O(h(n))$ and $g(n) = \Omega(h(n))$, then $f(n) = O(g(n))$.

{\bf Answer:} True. Since $f(n) = O(h(n))$, there exist positive
constants $c_1$ and $n_1$ such that $f(n) \le c_1 h(n)$ for all $n
\ge n_1$.  Similarly, since $g(n) = \Omega(h(n))$, there exist
positive constants $c_2$ and $n_2$ such that $g(n) \ge c_2h(n)$ for
all $n \ge n_2$.  This implies that for all $n \ge \max\{n_1, n_2\}$,
$f(n) \le c_1 h(n) \le c_1 g(n)/c_2$.  Therefore, $f(n) = O(g(n))$.

\item[{\bf (c)}]
$f(n^2) = \Omega((f(n))^2)$.

{\bf Answer:} False.  Consider $f(n) = \lg n$.  Then, $f(n^2) = 2\lg
n$, while $(f(n))^2 = \lg^2 n$.  Clearly, $f(n^2) \neq
\Omega((f(n))^2)$, since 
\[
\lim_{n \rightarrow \infty} \frac{2\lg n}{\lg^2 n} = \lim_{n \rightarrow \infty} \frac{2}{\lg n} = 0.
\] 
\end{itemize}

{\bf 4. (3 $\times$ 6 = 18 points)} Parts~(a),~(f), and~(g) of Problem
4--1, page 72.
\begin{itemize}
\item[{\bf (a)}] $T(n) = 2T(n/2) + n^3$.
  
  {\bf Answer:} We use the master method.  Here, $n^{\log_b a} = n$
  and $f(n) = n^3$.  This implies case~3 with $\eps = 2$.  Also, the
  additional condition for case~3 is satisfied since $2(n/2)^3 \le
  n^3/4$.  Therefore, we have $T(n) = \Theta(n^3)$.

\item[{\bf (b)}] $T(n) = 2T(n/4) + \sqrt{n}$.
  
  {\bf Answer:} We again use the master method.  Here, $n^{\log_b a} =
  \sqrt{n}$ and $f(n) = \sqrt{n}$.  Therefore, case~2 applies and we
  get $T(n) = \Theta(\sqrt{n} \lg n)$.

\item[{\bf (g)}] $T(n) = T(n - 1) + n.$

{\bf Answer:} We use the iteration method.  
\begin{eqnarray*}
T(n) & = & T(n - 1) + n\\
& = & T(n - 2) + n - 1 + n\\
& = & T(1) + 2 + 3 + 4 + \ldots + n - 1 + n\\
& = & \Theta(1) + n(n+1)/2\\
& = & \Theta(n^2).
\end{eqnarray*}
\end{itemize}

{\bf 5. (24 points)} The first $n$ cells of the array $E$ contain
integers sorted in increasing order.  The remaining cells all contain
some very large integer that we may think of as infinity (call it {\it
  maxint}).  The array may be arbitrarily large (you may think of it
as infinite), and you {\em do not know}\/ $n$.  Give an algorithm to
find the position of a given integer $x$ ($x < \mbox{{\it maxint}}$)
in the array in $O(\log n)$ time.

{\bf Answer:} Our algorithm consists of two phases.  In the first
phase, we find a location $k$ that is at least $n$ and at most $2n$.
In the next phase, we perform binary search for integer $k$ in
$E[1..k]$.

The first phase consists of the following iterative procedure.  In the
$i$th iteration, we check whether $E[2^{i-1}]$ is {\it maxint}.  If it
is, then we exit the procedure; otherwise, we continue to the next
iteration.  This first phase completes in the earliest iteration $j$
when $2^{j - 1} \ge n$.  That is, $2^{j - 1} \le 2n$, implying that $j
\le \lg n + 2$.  Thus, the running time of the first phase is $O(\lg
n)$.

In the second phase, we perform binary search for $x$ in
$E[1..2^{j-1}]$, which takes $O(\lg (2^{j-1}))$ steps, which is $O(j)
= O(\lg n)$ time.
\end{document}
