%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 2
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{25} \textbf {Asymptotic Notation}

Determine which of the eight choices below best describes each
function's asymptotic behavior.  No proofs are necessary.  {\bf (5
points each)}

\begin{tabbing}
XXX\=XXXXXXXXXXXX\=\kill
\>$\theta (n)$\>$\theta (n!)$\\
\>$\theta (n\log n)$\>$\theta (n^2)$\\
\>$\theta (1)$\>$\theta (2^n)$\\
\>$2^{\theta(n)}$\>None of the above
\end{tabbing}

\problempart  $g(n) = n + \ln n + (\ln n)^2$.

\solution{\bigskip
{\bf Solution:}

$\theta(n)$

We know that for sufficiently large $n$, $n > (\ln n)^2 > \ln n$.  
(For instance, if $n > e^2$ then $(\ln n)^2 = 4 < e^2$.)  Thus,
for sufficiently large $n$, 

$$n + \ln n + (\ln n)^2 < n + n + n = 3n.$$

Furthermore, as long as $\ln n$ is positive, 

$$n + \ln n + (\ln n)^2 > n.$$

Thus, for all sufficiently large $n$,  $n < g(n) < 3n$, so $g(n) = 
\theta(n)$.  
}

\smallspace
\problempart $h(n) = \frac{n^2 + 2n - 3}{n^2 - 1}$

\solution{\bigskip
{\bf Solution:}

$\theta(1)$

Dividing the top and bottom by $n-1$ yields

$h(n) = \frac{n+3}{n+1}$.  

Now, since the top is greater than the bottom, $h(n) > 1$ for all $n > -1$.
Furthermore, solving the equation $\frac{n+3}{n+1} < 2$ yields the solution
$n > 1$.  So for all $n > 1$, $h(n) < 2$.  

Thus, for all $n > 1$, we have $1 < h(n) < 2$ so $h(n) = \theta(1)$.
}

\smallspace
\problempart $j(n) = \sum_{i = 0}^n 2^{2i+1}$

\solution{\bigskip
{\bf Solution:}

$2^{\theta(n)}$

Putting the summation in closed form yields $j(n) = 2(4^n)/3$.

Now certainly, $\log_2 j(n) = \log_2(2/3) + n\log_2(4) = \theta(n)$.  Thus, 
$j(n) = 2^{\theta(n)}$.  However, as we showed in tutorial, $\neg (4^n = 
O(2^n))$ so $\neg (j(n) = \theta(2^n))$.  So $2^{\theta(n)}$ best 
describes
the asymptotic behavior of $j(n)$. 
}

\smallspace
\problempart $k(n) = (2 + \sin (n))2^{n + \sin(n)}$.

\solution{\bigskip
{\bf Solution:}

$\theta(2^n)$

We know that $\sin n \geq -1$ so $k(n) \geq (2-1)2^{n-1} = \frac122^n$.

We also know that $\sin n \leq 1$ so $k(n) \leq (2+1)2^{n+1} = 6\cdot2^n$.

Thus, $\frac12 2^n \leq k(n) \leq 6\cdot2^n$, so $k(n) = \theta(2^n)$.
}

\smallspace
\problempart $f(n) = \ln ((n^2)!)$.

\solution{\bigskip
{\bf Solution:}

None of the above.

By Stirling's approximation, we know that $l(n) = \theta(n^2 \ln n^2) =
\theta (n^2 \ln n)$.  Now, this grows faster than $\theta(1), \theta(n),
\theta(n^2)$ and $\theta(n \log n)$, and slower than $\theta(n!),
\theta(2^n)$ and $2^{\theta(n)}$, so ``none of these'' is the correct
answer. 

}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\problem {\bf (8 points)}  Order the functions listed below so that each
function is either $O$ or $\Theta$ of the next function.  Indicate
whether the stronger $\Theta$ relationship holds in each case.  No
proofs are required.

\begin{itemize}
\item $F_n$, the $n$-th Fibonacci number
\item $G(n)$, the number directed graphs with vertices
 $\{ 1, 2, 3, \ldots, n \}$ (self-loops permitted)
\item $P(n)$, the number of permutations of an $n$-element set
\item $M(n)$, the number of $n \times n$ matrices with only 0's and 1's
as elements
\end{itemize}

\solution{We rewrite these quantities in simpler forms to make
comparison possible.  First, $F_n$, the $n$-th Fibonacci number is
equal to:

\begin{eqnarray*}
F_n & = & \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n
    - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n \\
    & = &   \Theta\left(\left(\frac{1 + \sqrt{5}}{2}\right)^n\right)
\end{eqnarray*}

The $\Theta$ relation holds because the second term on the right
approaches zero.  The quantity $(1 + \sqrt{5}) / 2$ is $1.618\ldots$,
but any approximation between 1 and 2 will suffice for this problem.

Next, consider $G(n)$.  The possible edge sets of a directed graph
with vertices $\{1, 2, 3, \ldots, n\}$ are the subsets of $\{ 1, 2, 3,
\ldots, n \} \times \{ 1, 2, 3, \ldots, n \}$.  By the product rule and
the formula for the size of a power set, there are $2^{n^2}$ possible
directed graphs.

The number of permutations of an $n$-element set, $P(n)$, is $n!$,
which is bounded above and below by

\begin{eqnarray*}
\left( \frac{n}{e} \right)^n & \leq n! \leq & \left( \frac{n+1}{e} \right)^{n+1}.
\end{eqnarray*}

The number of entries in an $n \times n$ matrix is $n^2$ by the
product rule.  Therefore, $M(n)$, the number of $n \times n$ matrices
with 0-1 entries, is $2^{n^2}$

Putting all these facts together, we find that:

\begin{eqnarray*}
F_n & = &   O(P(n)) \\
P(n)    & = &   O(G(n)) \\
G(n)    & = &   \Theta(M(n)) \\
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (12 points)} Find a closed-form expression for $T(N)$ in
each problem part.  Your answer may make use of $\Theta$ notation.  No
proofs are required.

\begin{problemparts}

\problempart {\bf (6 points)}

\begin{eqnarray*}
T(n)    & = &   \sum_{i=1}^n \frac{i^2 + 6 \sqrt{i}}{i \sqrt{i}}
\end{eqnarray*}

\examonly{\vspace{2.5in}}

\solution
{
\begin{eqnarray*}
T(n)    & = &   \sum_{i=1}^n \frac{i^2 + 6 \sqrt{i}}{i \sqrt{i}} \\
    & = &   \sum_{i=1}^n \frac{i^2}{i \sqrt{i}} +
        \sum_{i=1}^n \frac{6 \sqrt{i}}{i \sqrt{i}} \\
    & = &   \sum_{i=1}^n \sqrt{i} +
        \sum_{i=1}^n \frac{6}{i} \\
    & = &   \Theta\left(n^{3/2} + \ln n\right) \\
    & = &   \Theta\left(n^{3/2}\right)
\end{eqnarray*}
}

\problempart {\bf (6 points)}

\begin{eqnarray*}
T(n)    & = &   \left\{
\begin{array}{cl}
1   &   \text{for} \quad n \leq 5 \\
\frac{1}{2} T(\left\lfloor\frac{n}{2} + \log{n}\right\rfloor) + \frac{2}{n}
    &   \text{for} \quad n > 5
\end{array}
\right.
\end{eqnarray*}

\solution{ We apply Akra-Bazzi.  First, we find the parameter $p$ by
solving the equation

\begin{eqnarray*}
\frac{1}{2} \cdot \left( \frac{1}{2} \right)^p  & = &   1.
\end{eqnarray*}

The solution is $p = -1$.  Therefore, we have

\begin{eqnarray*}
T(n)    & = &   \Theta\left(n^{-1} \cdot \left(
    1 + \int_1^n \frac{\left(\frac{2}{u}\right)}{u^{-1 + 1}} \ du
    \right)\right) \\
    & = &   \Theta\left(n^{-1} \cdot \left(
    1 + 2 \ln n
    \right)\right) \\
    & = &   \Theta\left(\frac{\ln n}{n}\right)
\end{eqnarray*}
}

\end{problemparts}
