\documentclass{article}
\begin{document}


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

\noindent
This assignment is due at the beginning of class on Mon., Sept. 10.  You may collaborate
with your classmates to complete this assignment but you must cite your collaborators.  In addition,
you must do your own write-up.  This assignment is worth 20 points (0 points if handwritten).


\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$
\item
$f(n)=n/10$ and $g(n)=10 \lg n$  (i.e. $\log_2$)
\item
$f(n)=sin(2\pi n)$ and $g(n)=cos(2\pi n)$
\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)$
\end{description}
\item
$f(n)=\log_3 n^2$, $g(n)=2 \lg n$

\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}$
\item
$\log_a^k n = k \log_a n$
\item
$\log_a n^k = k\log_a n$
\item
$\log_a n = \log_a b \; * \; \log_b n$
\end{enumerate}

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

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


\end{document}
