\documentclass{article}
\pagestyle{empty}

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

\noindent
This assignment is due at the start of class on Wed., Sept. 12.  You may collaborate
in small groups ($<5$) to complete this assignment but you must reference your collaborators.  
You may not consult solutions to old assignments or exams for CS140 to complete this assignment.
You must do your own write-up.  This assignment is worth 50 points (35 points if handwritten).  

\begin{enumerate}

\item
For every positive integer $n$, algorithm $A$ takes $3n^2$ steps on some input of size $n$.
State whether or not this statement implies the following.
\begin{enumerate}
\item
Algorithm $A$ is $O(n^3)$.

Ans.  No
\item
Algorithm $A$ is $\theta(n^2)$.

Ans. No
\item
Algorithm $A$ is $\Omega(n^2)$.

Ans. Yes
\end{enumerate}

\vspace{.5 in}

\item
Fill in the table with Y/N to the question $f(n)= {\cal X} (g(n))$ where
${\cal X}=O, \Omega, \Theta, o, \omega$.  Assume that $\epsilon, k$ and $c$ are
constants satisfying the following: $\epsilon > 0$,
$k > 1$,  and $c>1$.

\begin{tabular}{|l| l || l | l | l | l | l |} \hline
$f(n)$  & $g(n)$        & $O$   & $\Omega$      & $ \Theta $    & $o$   & $\omega$       \\[.1 in]  \hline
$n^{\epsilon}$  & $\log^k n$    & N &  Y &  N & N & Y \\[.1 in]  \hline
$n^k$   & $c^n$                 & Y & N  & N & Y  & N \\[.1 in] \hline
$n^{\lg c}$     & $c^{\lg n}$   & Y & Y & Y  & N & N\\[.1 in] \hline
$n^k$   & $ n^{2k}$             & Y & N  & N  & Y  & N \\[.1 in] \hline
$n^k$   & $ (n/c)^k$            & Y & Y  & Y  & N  & N  \\[.1 in] \hline
$c^n$   & $ c^{n+k}$            & Y & Y  & Y  & N  & N \\[.1 in] \hline
\end{tabular}

\vspace{.5 in}

\item
Which of the functions in the previous table are polynomially bounded?  

Ans.  $n^{\epsilon}, \; \log^k n, \; n^k, \; n^{\lg c}, \; c^{\lg n} , \; n^k, \; n^{2k}, \; (n/c)^k.$ 

For which
does $f(2n)=O(f(n))$?

Ans. Same as in previous part.

\vspace{.5 in}

\item
Compute the running time of the following algorithm.

{\tt algorithm} what($n$)
\begin{list}{}{}
\item {\hskip .2in \tt for $i=1$ to $\lfloor\sqrt{n}\rfloor$ do \hfill}
\item {\hskip .4in \tt for $j=\lfloor\sqrt{n}\rfloor$ downto $1$ do \hfill}
\item {\hskip .6in \tt for $k=1$ to $j$ do \hfill}
\item {\hskip .8in $\{\ O(1)$ time sequence of statements $\}$ \hfill}
\item {\hskip .6in \tt end \hfill}
\item {\hskip .4in \tt end \hfill}
\item {\hskip .2in \tt end \hfill}
\end{list}
{\tt end algorithm}

Ans. $O(n^{3/2})$





\end{enumerate}
\end{document}

