\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{courseMacros}

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

\head{1390}{Algorithms}{Winter 2001}{11 January 2001}{6}

\begin{center}
\Large{\bf Problem Set 1 (due January 18)}
\end{center}

{\bf 1. (15 points)} Exercise 1.25, page 63.

{\bf 2. (15 points)} The first $n$ cells of an array 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.  What is the worst-case running time of your algorithm?  Make
your algorithm as efficient, in terms of its worst-case running time,
as possible.  ({\em Hint:} The problem can be solved in $O(\lg n)$
time.)

{\bf 3. (10 points)} Problem 1.28, page 64.

{\bf 4. (15 points)} Arrange the following functions in order from the slowest
growing function to the fastest growing function.  Briefly justify
your answers.  ({\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^{1/2} \hs \hs n^2 + \lg n \hs \hs n(\lg n)^5 \hs \hs (\lg\lg n)^2
\hs \hs \lg
n\]

{\bf 5. (15 points)} The {\em Fibonacci numbers}\/ are defined by the
following recurrence.
\begin{eqnarray*}
F_0 & = & 0\\
F_1 & = & 1, \mbox{ and}\\
F_i & = & F_{i-1} + F_{i-2} \mbox{ for } i \ge 2.
\end{eqnarray*}

Prove by induction that for any $n \ge 2$, $F_n$ equals
$A^{n-1}_{1,1}$, where $A^n$ is the $n$th power of the following
matrix.
\[
A = \left( 
\begin{array}{cc}
1 & 1\\ 
1 & 0
\end{array}
\right)
\]

{\bf 6. (2 $\times$ 5 = 10 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) = \Omega(h(n))$ and $g(n) = \Omega(h(n))$, then $f(n) = \Theta(g(n))$.
\end{itemize}

\end{document}