\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSU690}{Algorithms and Data}{Spring 2005}{10 January 2005}{2}

\begin{center}
\Large{\bf Problem Set 1 (due Wednesday, January 19)}
\end{center}

{\bf 1. (6 points) Twenty questions}

A friend challenges you to find out a positive integer number $n$ that
she has on her mind.  For any guess you make, she is willing to tell
you which of the following three possibilities is true: $n$ is less
than, greater than, or equal to your guess.  You have no clue as to
how large $n$ is and would like to determine $n$ with the smallest
number of guesses.  

Describe a guessing procedure for determining $n$.  What is the number
of guesses your procedure makes, as a function of $n$?  You must aim
at keeping this function as small as possible.

{\bf 2. (1 + 5 + 5 + 3 = 14 points) Bubblesort}

Problem 2-2, page 38. 

{\bf 3. (1 + 3 + 6 = 10 points) Inversions and insertion sort}

Parts (a) through (c), Problem 2-4, pages 39-40.

{\em Hint for part (c):} If $T(A)$ is the running time of insertion
sort on input $A$ of $n$ numbers and $I(A)$ is the number of
inversions in $A$, then prove that $T(A)$ is $\Theta(I(A) + n)$.

{\bf 4. (10 points) Ordering functions} 

Arrange the following functions in order from the slowest growing
function to the fastest growing function.  Briefly justify your
answers.  ({\em Hint:} It may help to plot the functions and obtain an
estimate of their relative growth rates.  It may also help to express
each function as a power of $2$ and then compare.)

\[ n^{1/2} \hs \hs n^2 + \lg n \hs \hs n(\lg n)^5 \hs \hs (\lg\lg n)^2
\hs \hs \lg n\]

{\bf 5. (3 + 3 + 4 = 10 points) Properties of asymptotic notation}

Let $f(n)$, $g(n)$, and $h(n)$ be asymptotically positive and
monotonically increasing functions.  Prove or disprove each of the
following conjectures.
\begin{itemize}
\item[{\bf (a)}]
$f(n) + g(n) = \Theta(\min\{f(n), g(n)\})$.

\item[{\bf (b)}]
If $f(n) = O(h(n))$ and $g(n) = \Omega(h(n))$, then $f(n) = O(g(n))$.

\item[{\bf (c)}]
$f(n^2) = \Omega((f(n))^2)$.
\end{itemize}
\end{document}

