
\documentstyle{article}
\topmargin=-25pt
\oddsidemargin=-.25in
\evensidemargin=-.25in
\textheight=9in
\textwidth=7in
\begin{document}





\title{COT 5407 Introduction to Algorithms}
\author{Homework 1}
\date{DUE: Thursday September 6, 2012 at 11:00 AM}

\maketitle

{\em Please remember that all submissions must be typeset.
Handwritten submissions will NOT be accepted.
These must be uploaded to SCIS moodle in PDF format only}


\begin{enumerate}

\item
Order the following function by growth rate.
$N$, $\sqrt N$, $N ^ {1.5}$, $N^2$, $N \log N$, $N \log \log N $,
$N \log ^2 N $,
$N \log ( N ^ 2 ) $, $ 2/ N $, $2 ^ N$, $2 ^ {N/2}$, 37, $N^2 \log N$, $N^3$.
Indicate which functions grow at the same rate.


\item
An algorithm takes 0.5 ms for input size 100. How long will it take for
input size 500 if the running time is the following (assume low-order terms are
negligible):

\begin{enumerate}
\item
linear
\item
$O( N \log N )$
\item
quadratic
\item
cubic
\end{enumerate}



\item
An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in one minute 
if the running time is the following (asume low-order terms are
negligible):

\begin{enumerate}
\item
linear
\item
$O( N \log N )$
\item
quadratic
\item
cubic
\end{enumerate}


\item
Solve the following equations, expressing the answer in Big-Oh notation,
Assume that $T(N)$ is constant for sufficiently small $N$.

\begin{enumerate}
\item
$T(N) = T(N/2) + 1$

\item
$T(N) = T(N - 1) + \log N$

\item
$T(N) = T(N - 1) + N$

\item
$T(N) = 8T(N/2) + N^2$

\item
$T(N) = 8T(N/2) + N^3$

\item
$T(N) = 8T(N/2) + N^4$
\end{enumerate}

\item
{\em Three-way partitioning}
is a modification of quicksort that
partitions elements into groups smaller than,
equal to, and larger than the pivot.
Only the groups of smaller and larger elements need to be recursively sorted.
Show that if there are $N$ items but only $k$ unique values (in other words
there are many duplicates), then the running time of this modification to
quicksort is
$O( N k ) $. 


\item
You are given $N$ numbers.
Give an $O( N ^ 2 )$ algorithm to decide if there are
three numbers $a$, $b$, $c$ in the group that
satisfy $a + b = c$.

\end{enumerate}
\end{document}

