\documentclass[12pt]{article}

\usepackage{fullpage}

\begin{document}
\begin{center}
\bf
Algorithms Section 2\\
Spring 2003\\
\rm
Homework 3a\\
Due Thursday, February 6\\
\end{center}
\vspace{0.5cm}

\begin{enumerate}
 
\item \textbf{[15 Points] Professor Lai's Dot Product Algorithm.}
 Let $a = [ a_1, a_2, \dots, a_n ]$ and $b = [ b_1, b_2, \dots, b_n ]$ be
two arrays of
length $n$ where each $a_i$ and $b_i$ is a floating point number.
The \emph{dot product} of these arrays is defined to be $a_1 b_1 + a_2 b_2
+ \dots + a_n b_n$.
Professor Lai knows that he can compute the dot product in $O(n)$ time by
just taking the product
$a_i b_i$ for each $1 \leq i \leq n$ and then adding these terms up.
However, he is interested
in analyzing the
following recursive implementation which took him only a few minutes to
write.

\begin{verbatim}
float dot-product([a_1, a_2, ... , a_n], [b_1, b_2, ... , b_n])
{
  if (n == 1) return a_1 * b_1
  else
  {
     x = dot-product([a_1, ... , a_(n/2)], [b_1, ... , b_(n/2)]);
     y = dot-product([a_(n/2 + 1), ... , a_n], [b_(n/2 + 1), ... , b_n]);
     return x+y;
  }
}
\end{verbatim}
(The notation \verb+a_i+ or \verb+b_i+ in the program corresponds to $a_i$
or $b_i$.)
  \begin{enumerate}
  \item Set up a recurrence relation for this recursive program, solve it
(showing all of your
work), and give the running time in big-Oh notation as a function of $n$.

  \item Asymptotically, how does the running time of this program compare
to the standard $O(n)$
implementation?
  \end{enumerate}

\item \textbf{[15 Points] Sorting Variable-Length Items}
Solve Exercise 8.3 of Cormen \emph{et al.} second edition (page 179).

\item \textbf{[Optional 10 Points] More Recurrence Examples}
Solve recurrence f and h in Exercise 4.1 of Cormen \emph{et al.} second edition (page 85).

\end{enumerate}
\end{document}

