\documentclass{article}
\begin{document}


\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Fall 2001}\\
\vspace{.3 in}
{\large Solutions to Assignment 0}
\end{center}



\begin{enumerate}
\item
For each of the following functions $f(n)$ and $g(n)$ state the ranges
of positive integers for which
\begin{description}
\item[(i)]
$f(n) < g(n)$
\item[(ii)]
$f(n) = g(n)$
\item[(iii)]
$f(n) > g(n)$
\end{description}
For example, if $f(n)=2n$ and $g(n)=2^n$ then 
(i) hold in the range $[3,\infty)$, (ii) holds in the
range $[1,2]$, and (iii) fails to hold for any positive 
integers.
\begin{enumerate}
\item
$f(n)=10n$ and $g(n)=3^n$

Ans.  (i) $[4,\infty)$  (ii) $[]$,  (iii) $[1,3]$,
\item
$f(n)=n/10$ and $g(n)=10 \lg n$  (i.e. $\log_2$)

Ans.  (i) $[2,995]$, (ii) [], (iii) $[1],[996,\infty]$

\item
$f(n)=sin(2\pi n)$ and $g(n)=cos(2\pi n)$

Ans. $sin(2\pi n)=0$ and $cos(2\pi n)=1$ for all positive integers $n$ so
(i) $[1,\infty)$

\item
In this case the functions are defined recursively
as follows:
\begin{description}
\item[$n=1$:]
$f(n)=1$,
$g(n)=1$
\item[$n>1$ and even:]
$f(n)=f(n-1)$, $g(n)=2^{f(n-1)}$
\item[$n>1$ and odd:]
$f(n)=2^{g(n-1)}$, $g(n)=g(n-1)$

Ans.  (i) $\{2,4,8,\ldots\}$, (ii) $[1]$, (iii) $\{3,5,7,\ldots\}$
\end{description}
\item
$f(n)=\log_3 n^2$, $g(n)=2 \lg n$

Ans. (i) $[2, \infty]$, (ii) $[1]$, (iii) $[]$

\end{enumerate}

\item
Identify the following statements as true or false.
You may assume that $a,w,k$ and $n$ are positive real
numbers. 
\begin{enumerate}
\item
$w=a^{\log_a w}$

Ans. True
\item
$\log_a^k n = k \log_a n$

Ans. False
\item
$\log_a n^k = k\log_a n$

Ans. True
\item
$\log_a n = \log_a b \; * \; \log_b n$

As. True
\end{enumerate}

\item
Give an example of a function $f: {\cal N} \rightarrow {\cal N}$
such that $lim_{n \rightarrow \infty} f(n)$ exists.

One possible ans. $f(n)= 3$

\item
Give an example of a function $f: {\cal N} \rightarrow {\cal N}$
such that $lim_{n \rightarrow \infty} f(n)$ does not exist.

One possible ans. $f(n)=n$
\end{enumerate}


\end{document}
