\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}{Fall 2006}{8 September 2006}{1}

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

{\bf 1. (4 points)} Chapter 1, Exercise 1, page 22.

{\bf 2. (12 points)} Chapter 1, Exercise 4, page 23.

{\bf 3. (10 points) Recursion and induction in binary codes}

Digital transmission protocols transmit signals using binary codes.
In order to minimize the effect of errors, it is often useful to
select a code such that ``similar'' signals use ``similar'' codewords.

One such code is a list of $2^n$ $n$-bit strings in which each string
(except the first) differs from the previous one in exactly one bit.
Let us call such a list a {\em twiddling list} since we go from one
string to the next by just flipping one bit.

Consider the following recursive algorithm for listing the $n$-bit
strings of a twiddling list.  If $n = 1$, the list is 0,1.  If $n >
1$, first take a twiddling list of $(n-1)$-bit strings, and place a 0
in front of each string.  Then, take a second copy of the twiddling
list of $(n-1)$-bit strings, place a 1 in front of each string,
reverse the order of the strings and place it after the first list.
So, for example, for $n = 2$, the list is 00,01,11,10, and for $n=3$,
we get 000,001,011,010,110,111,101,100.

Prove by induction on $n$ that (a) every $n$-bit string appears
exactly once in the list generated by the algorithm, and (b) each
string (except the first) differs from the previous one in exactly one
bit.

{\bf 4. (12 points)} Chapter 2, Exercise 6, page 68.

{\bf 5. (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.  In some cases, it may also
help to express the functions as a power of $2$ and then compare.)

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

{\bf 6. (3 $\times$ 4 = 12 points) Properties of asymptotic notation} 

Let $f(n)$, $g(n)$, and $h(n)$ be asymptotically positive and
monotonically increasing functions.  For each of the following
statements, decide whether you think it is true or false and give a
proof or a counterexample.
\begin{itemize}
\item[{\bf (a)}] 
$f(n) + g(n) = \Theta(\max\{f(n), g(n)\})$.

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

\item[{\bf (c)}] 
If $f(n) = O(g(n))$, then $f(n)^2$ is $O(g(n)^2)$.
\end{itemize}
\end{document}

