\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment 4} \\ Due
Thursday, October 3 in Recitation
\end{center}
\begin{quote}
Truth is on a curve whose asymptote our spirit follows eternally.
\\ L\'eo Errera
\end{quote}
When asked for the asymptotics answer in a form $\Theta(n^a)$ or
$\Theta(\lg^bn)$ or $\Theta(n^a\lg^bn)$ for some reals $a,b$.
\ben
\item Consider the recursion
$T(n)=9T(n/3) + n^2$ with initial value $T(1)=1$. Calculate the
{\em precise} values of $T(3),T(9),T(27),T(81),T(243)$. Make a good
(and correct) guess as to the general formula for $T(3^i)$ and
write this as $T(n)$. (Don't worry about when $n$ is not a power
of three.) Now use the Master Theorem to give, in Thetaland, the
asymptotics of $T(n)$. Check that the two answers are consistent.
\item Use the Master Theorem to give, in Thetaland, the asymptotics of
these recursions:
\ben
\item $T(n)= 6T(n/2) + n\sqrt{n}$
\item $T(n)= 4T(n/2)+n^5$
\item $T(n)= 4T(n/2)+7n^2+2n+1$
\een
\item {\tt Toom-3} is an algorithm similar to the
Karatsuba algorithm discussed in class. (Don't worry how
{\tt Toom-3} really works, we just want an analysis given the
information below.)
It multiplies two $n$ digit numbers by making five recursive calls
to multiplication of two $n/3$ digit numbers plus thirty additions
and subtractions. Each of the additions and subtractions take
time $O(n)$. Give the recursion for the time $T(n)$ for {\tt Toom-3} and
use the Master Theorem to find the asymptotics of $T(n)$. Compare with
the time $\Theta(n^{\log_23})$ of Karatsuba. Which is faster when $n$
is large?
\item Write the following sums in the form $\Theta(g(n))$ with $g(n)$
one of the standard functions.
In each case give reasonable (they
needn't be optimal) positive $c_1,c_2$ so that the sum is between
$c_1g(n)$ and $c_2g(n)$ for $n$ large.
\ben
\item $n^2+(n+1)^2+\ldots + (2n)^2$
\item $\lg^2(1)+\lg^2(2)+\ldots + \lg^2(n)$
\item $1^3+\ldots+n^3$.
\een
\item (Just for fun!) Name this Paul Simon tune:
\[ \forall_x\exists_y \lceil x \rceil = \lfloor y \rfloor \]
(websearch encouraged.)
\item Give an algorithm for subtracting two $n$-digit decimal numbers.
The numbers will be inputted as $A[0\cdots N]$ and $B[0\cdots N]$
and the output should be $C[0\cdots N]$. (Assume that the result will
be nonnegative.)
How long does your algorithm take, expressing
your answer in one of the standard $\Theta(g(n))$ forms.
\een
\begin{quote}
The mind is not a vessel to be filled but a fire to be kindled. \\ -- Plutarch
\end{quote}
\end{document}