\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{Winter 2000}{25 January 2000}{8}

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

\bigskip

%%% A poorly worded question.  It's a little tricky since the a_i's form an infinite sequence. 
%%% One may ask whether their being constants implies that there is an infimum and a supremum
%%% for the sequence.

{\bf 1. (10 points)} Let
\[
f(n) = \sum_{i = 0}^{n} a_i 2^i,
\]
where $a_0$ through $a_n$ are arbitrary real constants and $a_n > 0$.
Using the definition of $\Theta$-notation, prove that $f(n) =
\Theta(2^n)$.

{\bf Answer:} A number of students raised valid complaints about the
meaning of ``$a_0$ through $a_n$ are arbitrary real constants''.
Basically, what I had meant was they are bounded and since we require
$a_n > 0$, it effectively implies that all the $a_i$'s are {\em
  bounded}\/ positive constants.  (In the terminology of real
analysis, the infimum and the supremum of the sequence of $a_i$'s
exist and they are both positive.)

So, if we let $m$ and $M$ be the lower and upper bounds, respectively,
we get
\[
m \sum_{i = 0}^n 2^i \le f(n) \le M \sum_{i = 0}^n 2^i,
\]
which yields 
\[
m 2^n \le f(n) \le M 2^{n+1},
\]
thus giving us the result.

{\bf 2. (10 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 express each function as a power of $2$
and then compare.)

\[ 
n^{\lg\lg n} \hs (\frac{3}{2})^{2n} \hs 2^{\lg^2 n} \hs n^{100}
\]

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

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

{\bf 3. (3 $\times$ 5 = 15 points)} Prove or disprove each of the
following conjectures.
\begin{itemize}
\item[{\bf (a)}] If $f(n)$ is a polynomial in $n$, then $f(n^2)$ is
  $\Theta((f(n))^2)$.
  
  {\bf Answer:} True.  If $f(n)$ is a polynomial, then $f(n) =
  \Theta(n^d)$, for some real constant $d > 0$.  That is, there exist
  positive real constants $c_1$ and $c_2$ and positive integer
  constant $n_0$ such that $c_1 n^d \le f(n) \le c_2 n^d$ for all $n
  \ge n_0$.  Since $n \ge n_0$ implies $n^2 \ge n_0$, we have for all $n \ge n_0$
  \begin{eqnarray}
    \label{eqn:3.1}
    c_1 n^{2d} \le f(n^2) \le c_2 n^{2d}.
  \end{eqnarray}
  Furthermore, we have for all $n \ge n_0$
  \begin{eqnarray}
    \label{eqn:3.2}
    c_1^2 n^{2d} \le (f(n))^2 \le c_2^2 n^{2d}.
    \end{eqnarray}
    We obtain from Equations~\ref{eqn:3.1} and~\ref{eqn:3.2} that for all $n
    \ge n_0$
    \[c_1 (f(n))^2 /c_2^2 \le (f(n))^2 \le c_2 (f(n))^2/c_1^2.\]

    This proves that $f(n^2) = \Theta((f(n))^2)$.

\item[{\bf (b)}] Let $f(n)$, $g(n)$, and $h(n)$ be asymptotically
  positive and monotonically increasing functions.  If $g(n) =
  \Theta(h(n))$, then $f(n)^{g(n)} = \Theta(f(n)^{h(n)})$.
  
  {\bf Answer:} False.  Take $f(n) = n$, $g(n) = n$ and $h(n) = 2n$.
  Clearly, $g(n) = \Theta(h(n))$.  The function $f(n)^{g(n)}$ equals
  $n^n$, while the function $f(n)^{h(n)}$ equals $n^{2n}$.  The ratio
  of the two functions equals $1/n^n$ which tends to zero as $n$ tends
  to infinity.  Therefore, $f(n)^{g(n)} = o(f(n)^{h(n)}) \neq
  \Theta(f(n)^{h(n)})$.

\item[{\bf (c)}] Let $f(n)$ and $g(n)$ be asymptotically positive and
  monotonically increasing functions.  Then, $f(n) + g(n) =
  O(\max\{f(n), g(n)\})$.
  
  {\bf Answer:} True.  For all $n \ge 0$, $f(n) + g(n) \le 2
  \max\{f(n), g(n)\}$.  This proves the desired claim.

\end{itemize}

{\bf 4. (5 + 10 + 5 + 5 = 25 points)} Problem 1--2, page 17.

\begin{itemize}
\item[{\bf (a)}] Insertion sort of $k$ elements takes $\Theta(k^2)$
  time in the worst-case.  There are $n/k$ lists of $k$ elements.
  Therefore, the total time taken for insertion sort is
  $(n/k)\Theta(k^2) = \Theta(nk)$.
  
\item[{\bf (b)}] We first group the $n/k$ lists into $n/(2k)$ pairs of
  two lists each, and merge each pair separately into a sorted list of
  length $2k$.  We thus obtain $n/(2k)$ groups of $2k$ elements each.
  We iterate this so that after the $i$th iteration, we have
  $n/(2^ik)$ sorted lists of $2^i k$ elements each.  Thus, after
  $\lg(n/k)$ iterations, we have a single sorted list of length $n$.
  
  The running time of the $i$th iteration equals the running time of
  $n/(2^i k)$ merges, each applied to a pair of lists of size $2^i k$.
  The worst-case running time of each such merge is $\Theta(2^i k)$.
  Therefore, the worst-case running time of iteration $i$ is
  $\Theta(n)$.  Since the number of iterations is $\lg(n/k)$, the
  total worst-case running time is $\Theta(n\lg (n/k))$.
  
  {\em Remark:} In the above analysis, we have ignored floors and
  ceilings for simplicity.  It is important to note, however, that we
  can avoid this simplifying assumption and still obtain the same
  bound since, after all, we are placing a $\Theta$-bound on the
  running time.
  
\item[{\bf (c)}] From parts~(a) and~(b), the worst-case running time
  of modified mergesort is thus $\Theta(nk + n\lg (n/k))$.  For this
  running-time to compare favorably with mergesort, we need $nk$ and
  $n \lg(n/k)$ both to be $O(n \lg n)$.  For all values of $k$, $n
  \lg(n/k)$ is $O(n \lg n)$, while $nk$ is $O(n \lg n)$ only if $k$ is
  $O(\lg n)$.  Therefore, the largest asymptotic bound on $k$ such
  that the running-time of modified mergesort is asymptotically the
  same as mergesort is $\Theta(\lg n)$.
  
\item[{\bf (d)}] In practice, we need to pay attention to the hidden
  constants.  Let $c_1 nk$ denote the running-time of the insertion
  sort phase, while $c_2 n\lg(n/k)$ denote the running time of the
  merging phase, where $c_1$ and $c_2$ are positive constants.  We
  would like to select that value of $k$ that minimizes $c_1 nk + c_2
  n\lg(n/k)$.  This is minimized when $c_1 k - c_2 \lg k$ is
  minimized.  Taking the derivative with respect to $k$ and setting it
  to $0$, we obtain a local extrema at $k = c_1 \ln 2/c_2$.  Since the
  second derivative with respect to $k$ is positive, this is a local
  minima.  Thus, in practice, we will set $k$ to be $\approx c_1 \ln
  2/c_2$.
  
  {\em Remark:} In the above calculation, we assumed that the running
  times of the two phases are exactly given by $c_1 nk$ and $c_2
  n\lg(n/k)$, respectively.  This may not be true.  One can easily
  extend the same argument as above to a more precise analysis where
  we assume, for example, that the insertion sort phase takes $c_1 nk
  + c_3n + c_4k$, for some positive constant $c_1$ and arbitrary
  constants $c_3$ and $c_4$.  We can incorporate the new expressions
  and again find $k$ that minimizes the running-time, for a fixed $n$.
  This will give an expression for $k$, possibly in terms of $n$.
\end{itemize}

{\bf 5. (4 $\times$ 5 = 20 points)} Solve the following recurrences.
Assume that $T(n)$ is constant for $n \le 2$.  
\begin{itemize}
\item[{\bf (a)}]
$T(n) = T(n - 1) + \sqrt{n}$.

{\bf Answer:} Using the iteration method and assuming that $T(1) =
\Theta(1)$, we obtain 
\begin{eqnarray*}
T(n) & = & \Theta(1) + \sum_{i = 2}^n \sqrt{i}\\
& \le & \Theta(1) + n\sqrt{n},\\
\end{eqnarray*}
implying that $T(n) = O(n^{3/2})$.  We derive a lower bound similarly.
\begin{eqnarray*}
T(n) & = & \Theta(1) + \sum_{i = 2}^n \sqrt{i}\\
& \ge & \Theta(1) + \frac{n}{2} \sqrt{\frac{n}{2}}\\
& = & \Theta(1) + \frac{1}{2\sqrt{2}}n^{3/2}.
\end{eqnarray*}
implying that $T(n) = \Omega(n^{3/2})$.

{\em Remark:} We can also use the connection between summation and
integration to derive upper and lower bounds for the sum $\sum_i
\sqrt{i}$.

\item[{\bf (b)}] $T(n) = 4T(n/4) + n^2$.
  
  {\bf Answer:} We use the master theorem.  Here $f(n) = n^2$ and
  $n^{\log_b a} = n$.  Therefore, we can apply case~3 with $\eps = 1$.
  Furthermore, since $f(n) = n^2 \ge 4 \cdot 4f(n/4)$, the additional
  condition required for case~3 also holds.  We obtain $T(n) =
  \Theta(n^2)$.
  
\item[{\bf (c)}] $T(n) = T(\alpha n) + T((1 - \alpha)n) + n$, where
  $\alpha$ is a real constant in the range $0 < \alpha < 1$.  ({\em
    Hint:} Use a recursion tree.)
  
  {\bf Answer:} We use a recursion tree.  The contribution of the
  first level of the tree is $n$.  The contribution of the second
  level is $\alpha n + (1 - \alpha)n = n$.  The contribution of the
  third level is $\alpha^2 n + 2\alpha(1 - \alpha) n + (1 - \alpha)^2
  n = n$.  We can thus show that the contribution of $i$th level is
  $n$, as long as $i \le \min\{ \log_{1/\alpha} n, \log_{1/(1-\alpha)}
  n\}$.  Note that $\log_{1/\alpha} n$ is the distance of the root of
  the recursion tree to the leftmost leaf and $\log_{1/(1 -\alpha)} n$
  is the distance of the root of the recursion tree to the rightmost
  leaf.  Therefore, the total contribution is at most $n \max\{
  \log_{1/\alpha} n, \log_{1/(1-\alpha)} n\}$, thus indicating that
  $T(n) = O(n \lg n)$, since $\alpha$ is a constant.  Similarly,
  $T(n)$ at least $n \min\{ \log_{1/\alpha} n, \log_{1/(1-\alpha)}
  n\}$, thus implying that $T(n) = \Theta(n \lg n)$, since $\alpha$ is
  a constant.

\item[{\bf (d)}] $T(n) = T(n^{2/3}) + 5$.
  
  {\bf Answer:} We use the iteration method.  After applying $i$
  iterations we obtain

\[ T(n) = T(n^{(2/3)^i}) + 5i. \]

We assume that the iteration bottoms out when $n^{(2/3)^i} = 2$.  This
yields $i = \log_{3/2} \lg n = ( \lg \lg n)/\lg(3/2)$.  Since $T(2)$
is a constant, we obtain $T(n) = \Theta(1) + 5(\lg \lg n)/\lg(3/2) =
\Theta(\lg \lg n)$.
\end{itemize}
\end{document}

