\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 1999}{10 January 2000}{5}

\begin{center}
\Large{\bf Problem Set 1 (due January 18)}
\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 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 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)\})$.

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

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

{\bf 4. (3 $\times$ 6 = 18 points)} Parts~(a),~(f), and~(g) of Problem
4--1, page 72.

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