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

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

\head{1390}{Algorithms}{Winter 2001}{29 January 2001}{9}

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

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

{\bf Answer:} One can easily find the minimum and maximum by making
two passes through the array, first to find the minimum and next to
find the maximum.  This, however, takes $2(n-1)$ comparisons.  In
order to achieve a bound of $1.5 n$ comparisons, we need to perform an
average of at most 3 comparisons for every 2 elements.  To do this, we
maintain the minimum and maximum elements seen thus far.  Rather than
processing each element of the array by comparing it against the
current maximum and minimum, however, at the cost of 2 comparisons per
element, we process the elements in pairs.  We first compare the two
elements in a pair with each other, then compare the smaller of the 2
with the current minimum and the larger of the 2 with the current
maximum.  This incurs a cost of 3 comparisons every 2 elements, for a
total of $3n/2 = 1.5n$ comparisons.

{\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 Answer:} Let $A$ be the given array.  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 $x$ in $A[1..k]$.

The first phase consists of the following iterative procedure.  In the
$i$th iteration, we check whether $A[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
$A[1..2^{j-1}]$, which takes $O(\lg (2^{j-1}))$ steps, which is $O(j)
= O(\lg n)$ time.

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

{\bf Answer:} We use the relationship between asymptotic notation and
limits.  We derive
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{a_k n^k + a_{k-1}n^{k-1} + \ldots
a_1 n + a_0}{n^k} & = & a_k + \lim_{n\rightarrow \infty}
\frac{a_{k-1}}{n} + \ldots + \lim_{n\rightarrow \infty}
\frac{a_0}{n^k}\\
& = & a_k.
\end{eqnarray*}
Since $0 < a_k < \infty$, $p(n) = \Theta(n^k)$.

{\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 Answer:} The order from slowest growing to the fastest growing
function is: $(\lg \lg n)^2$, $\lg n$, $n^{1/2}$, $n$, and $n(\lg^5
n)$.  We prove this using four steps: (i) $(\lg \lg n)^2 = O(\lg n)$,
(ii) $\lg n = O(n^{1/2})$, (iii) $n^{1/2} = O(n)$, and (iv) $n =
O(n\lg^5 n)$.
\begin{itemize}
\item[(i)] We use the connection between asymptotic notation and
limits.  Let $m = \lg n$.  We get $(\lg \lg n)^2 = \lg^2 m$ and $\lg n
= m$.  So we are comparing $\lg^2 m$ and $m$.  As $n$ tends to
infinity, so does $m$.  Therefore, we calculate the following limit.
\begin{eqnarray*}
\lim_{m \rightarrow \infty} \frac{\lg^2 m}{m} & = & 
\lim_{m \rightarrow \infty} \frac{2 \lg m}{m\ln 2}\\
& = & \lim_{n \rightarrow \infty} \frac{2}{m \ln^2 2}\\
& = & 0.
\end{eqnarray*}
Note that we use L'Hopital's rule twice.  We thus obtain that $\lg^2 m
= O(m)$ yielding $(\lg \lg n)^2 = O(\lg n)$.

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

\item[(iii)] We again use the connection between asymptotic notation
  and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{n^{1/2}}{n} & = & 
\lim_{n \rightarrow \infty} \frac{1}{n^{1/2}}\\
& = & 0,
\end{eqnarray*}
Therefore, $n^{1/2} = O(n)$.

\item[(iv)] We again use the connection between asymptotic notation
  and limits.
\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{n}{n \lg^5 n} & = & 
 \lim_{n \rightarrow \infty} \frac{1}{\lg^5 n}\\
& = & 0.
\end{eqnarray*}
Therefore, $n = O(n \lg^5 n)$.
\end{itemize}


{\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 Answer:} We show by induction on $n \ge 1$ that:
\[
A^n = \left( 
\begin{array}{cc}
F_{n+1} & F_n\\
F_n & F_{n-1}
\end{array}
\right).
\]
Note that the above statement directly implies the desired claim in
this problem.

The induction base ($n = 1$) follows directly from the definition of $A$ and
the fact that $F_0 = 0$ and $F_1 = F_2 = 1$.

We now establish the induction step for $n = m \ge 2$ assuming that the claim holds
for all $n < m$.  We write $A^m$ as $A^{m-1} A$ and obtain:
\[
A^m  =  \left(
\begin{array}{cc}
F_m & F_{m-1}\\
F_{m-1} & F_{m-2}
\end{array}
\right)
\cdot
\left(
\begin{array}{cc}
1 & 1\\
1 & 0
\end{array}
\right)
= \left(
\begin{array}{cc}
F_m + F_{m-1} & F_m\\
F_{m-1} + F_{m-2} & F_{m-1}\\
\end{array}
\right)
= \left(
\begin{array}{cc}
F_{m+1} & F_m\\
F_m & F_{m-1}
\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)\})$.

{\bf Answer:} True.  We first note that since the two functions are
asymptotically positive, if $n$ is sufficiently large, then $f(n) + g(n) \ge
\max\{f(n), g(n)\}$.  Therefore, $f(n) + g(n) = \Omega(\max\{f(n), g(n)\})$.
For the other part, we note that $f(n) + g(n) \le 2 \max\{f(n), g(n)\}$ for
all $n$, thus implying that $f(n) + g(n) = O(\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))$.

{\bf Answer:} False.  Let $f(n) = n$, $g(n) = n^2$, and $h(n) = n$.
Then, $f(n) = \Omega(h(n))$ and $g(n) = \Omega(h(n))$, yet $f(n) = n
\neq \Theta(n^2) = \Theta(g(n))$.
\end{itemize}
\end{document}