\documentclass[12pt]{article}

\usepackage{fullpage}

\begin{document}
\begin{center}
\bf
Algorithms Section 2 \\
Computer Science 140 \& Mathematics 168 \\
Spring 2003 \\
\rm
Homework 2a\\
Due Thursday, January 30  \\
\end{center}
\vspace{0.5cm}

\begin{enumerate}
\item {\bf [25 Points] Fast Multiplication Circuits!}
In this problem we consider the problem of multiplying two $n$-bit numbers,
$x$ and $y$.  (For simplicity, assume that $n$ is a power of 2.  This
is generally the case anyhow in typical computer architectures, but
we could easily relax this assumption.)
\begin{enumerate}
        \item  Explain why the time complexity of the standard 
        algorithm (performing normal multiplication, only in base 2
rather than base 10) for this problem is $\Theta(n^{2})$. \\

        Some fast multiplication circuits use the
        following clever divide-and-conquer algorithm.  Divide $x$ and $y$
        in half.  Thus, $x = a 2^{n/2} + b$ and $y = c 2^{n/2} + d$ where
        $a, b, c, d$ are $n/2$-bit numbers.
        The product of $x$ and $y$, call it $z$, can now be computed by
        the following steps:
        \begin{enumerate}
                \item $temp1 = (a+b) \cdot (c+d)$
                \item $temp2 = a \cdot c$
                \item $temp3 = b \cdot d$
                \item $z = temp2 \cdot 2^{n} + (temp1 - temp2 - temp3) \cdot 2^{
n/2} + temp3$.
        \end{enumerate}
        \item Briefly explain why this algorithm
really gives us the desired product.

        \item Observe that the terms $(a+b)$ and $(c+d)$ may h
ave
either $\frac{n}{2}$ bits or $\frac{n}{2} + 1$ bits.  Assume (for now)
        that they each have exactly $\frac{n}{2}$ bits.         The above algorithm performs 3 multiplications of $n/2$ bit numbers plus
        some additions and shifts.  (Multiplying a binary number by a number
        $2^{\ell}$ can be accomplished by simply performing $\ell$ bit shifts
        to the left!  This takes $\Theta(\ell)$ time.)  
        Describe a recursive algorithm that uses this idea and
        write a recurrence relation for the time complexity, $T(n)$.
        \item  Find the asymptotic time complexity of
        the divide-and-conquer algorithm by using a recursion tree
analysis.  Show each step of your computation.  Your final answer should
be in the form $O(n^c)$ where $c$ is an \textbf{actual number}.  (In
other words, don't leave $c$ as some mathematical expression.)

        How does this algorithm compare
        asymptotically to the standard multiplication algorithm?
        \item Describe how the algorithm can be
        fixed to take care of the case that $a+b$ and $c+d$ are 
        possibly $n/2 + 1$-bit numbers.  (The algorithm should not
        be slower asymptotically after making this fix.)
\end{enumerate}
\end{enumerate}
\end{document}

