\documentclass[11pt]{article}
\usepackage{array}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\NIL}{{\tt NIL}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Problem Set 3\\
Solutions}
\end{center}
\ben
\item Write each of the following functions as $\Theta(g(n))$ where
$g(n)$ is one of the standard forms:
$2n^3-11n+98$ ;
$6n + 43n\lg n$;
$63n^2 + 14n\lg^5n$;
$3 + \frac{5}{n}$
\So In order, $\Theta(n^4),\Theta(n\lg n),\Theta(n^2),\Theta(1)$.
\item Illustrate the operation of {\tt RADIX-SORT} on the
list: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG,
TEA, NOW, FOX following the Figure in the Radix-Sort section.
(Use alphabetical order and sort one letter at a time.)
\So From left to right:
\begin{center}
% use packages: array
\begin{tabular}{llll}
COW & SEA & TAB & BAR \\
DOG & TEA & BAR & BIG \\
SEA & MOB & EAR & BOX \\
RUG & TAB & TAR & COW \\
ROW & DOG & SEA & DIG \\
MOB & RUG & TEA & DOG \\
BOX & DIG & DIG & EAR \\
TAB & BIG & BIG & FOX \\
BAR & BAR & MOB & MOB \\
EAR & EAR & DOG & NOW \\
TAR & TAR & COW & ROW \\
DIG & COW & ROW & RUG \\
BIG & ROW & NOW & SEA \\
TEA & NOW & BOX & TAB \\
NOW & BOX & FOX & TAR \\
FOX & FOX & RUG & TEA
\end{tabular}
\end{center}
\item Illustrate the operation of {\tt BUCKET-SORT} on the
array \\ $A=(.79,.13,.16,.64,.39,.20,.89,.53,.71,.43)$ \\ following
the Figure in the Bucket-Sort section.
\So We first construct the auxiliary list $B$:
\begin{center}
\begin{tabular}{|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|}
\hline
$\emptyset$ & $ \downarrow$ & $ \downarrow$ & $ \downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\emptyset$ \\
\hline & .13 & .20 & .39 & .43 & .53 & .64 & .79 & .89 & \\
\hline & $ \downarrow$ & & & & & & $\downarrow$ & & \\
\hline & .16 & & & & & & .71 & & \\
\hline
\end{tabular}
\end{center}
We then sort each bucket with any sort, giving us:
\begin{center}
\begin{tabular}{|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|}
\hline
$\emptyset$ & $ \downarrow$ & $ \downarrow$ & $ \downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\emptyset$ \\
\hline & .13 & .20 & .39 & .43 & .53 & .64 & .71 & .89 & \\
\hline & $ \downarrow$ & & & & & & $\downarrow$ & & \\
\hline & .16 & & & & & & .79 & & \\
\hline
\end{tabular}
\end{center}
Finally, we concatenate each of the buckets together in order:
\begin{center}
\begin{tabular}{|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|}
\hline .13 & .16 & .20 & .39 & .43 & .53 & .64 & .71 & .79 & .89 \\ \hline
\end{tabular}
\end{center}
\item Given $A[1\cdots N]$ with $0\leq A[I]I$.
So we need look at $\sqrt{1}+\ldots+\sqrt{N}$. This is at most $N\sqrt{N}$
as there are $N$ terms and each is at most $\sqrt{N}$. As a lower bound
cut it off at the middle. (This often works!) We have $\sqrt{N/2}+\ldots+
\sqrt{N}$. There are $N/2$ terms here and each is at least $\sqrt{N/2}$
so the total is at least $N\sqrt{N}/(2\sqrt{2})$. In Theta-World (as your
lecturer likes to call it) constants don't count so the answer is $\Theta(N^{3/2})$.
\item
FOR I = 1 to N
\\ \hsa J=I
\\ \hsa WHILE J $<$ N
\\ \hsb do J=2*J
\So For a given $I$ the subloop starts at $I$ and double until reaching $N$. We double
$t$ times, where $t$ is the smallest integer $I2^t\geq N$, so $t=\lceil \lg(N/I) \rceil$.
So the total time is
\beq TOTAL = O\left( \sum_{i=1}^n \lceil\lg(n/i)\rceil \right) \eeq
This is challenging.
\\ {\tt Approach One:} We ``get rid" of the ceiling by noting that the ceiling can only
affect each term by $1$ and therefore the sum by at most $n$ and so
\beq TOTAL = O(n)
+O\left( \sum_{i=1}^n \lg(n/i) \right)
\eeq
Now there are a variety of approaches. One is via Stirling's Formula. The object in
parentheses is precisely $\ln(n^n/n!)$ and by Stirling $n^n/n! \sim e^n(2\pi n)^{-1/2}$.
The square root term is inconsequential and $\lg(n^n/e^n) \sim n\lg 2 = O(n)$. Thus
\beq TOTAL = O(n) + O(n) = O(n) \eeq
this is a linear time algorithm! Note that the ceiling actually does have an effect
on the constants buried in the $O$ as both parts are linear in $n$. {\tt Comment:}
How did we know that removing the ceilings would work? We didn't, we tried it and
it turned out its effect was not dominant so we were OK. This is part of the {\em art}
of doing asymptotics!
\\ {\tt Approach Two:} Similar to the analysis of BUILD-MAX-HEAP we have $1$ doubling
$n/2$ times, $2$ doublings $n/4$ times ($n/4 < i \leq n/2$), $3$ doublings $n/8$ times
so the total doublings is $n \sum_u u2^{-u}$ but that sum, even to infinity, is $2$
so the total doublings is $\sim 2n$.
\een
\item Prof.\ Ligate decides to do Bucket Sort on $n$ items with $n^2$ buckets while
his student Ima Hogg decides to do Bucket Sort on $n$ items with $n^{1/2}$ buckets.
Assume that the items are indeed uniformly distributed. Assume that Ima's algorithm
for sorting inside a bucket takes time $O(m^2)$ when the bucket has $m$ items.
\ben
\item Argue that Prof.\ Ligate has made a poor choice of the number of buckets by
looking analyzing the time of Bucket Sort in his case.
\So The time will be $O(n^2)$ since one has to pass through the buckets
to link them up. Note that even though most of the buckets are empty
you don't know which one's are empty so you have to check each one.
\item Argue that Ima has made a poor choice of the number of buckets by
looking analyzing the time of Bucket Sort in her case.
\So Lets say each of the $n^{1/2}$ buckets had around $n^{1/2}$ items.
(Indeed, with high probability that will be the case.) Then sorting each
bucket (under our assumption) takes $O((n^{1/2})^2)=O(n)$ so the total
time for bucket sorting would be $O(n^{3/2})$.
\item Ima had tried to save space by using fewer buckets. Why was she wrong?
\So She didn't save any space. While the array is only of length
$n^{1/2}$ she has all the items in the linked lists in the array so the
total space used up by the array is still $\Theta(n)$.
\een
\een
\begin{quote}
If you take a number and double it and double it again and then double
it a few more times, the number gets bigger and bigger and goes higher
and higher and only arithmetic can tell you what the number is when
you quit doubling.
\\ from {\em Arithmetic} by Carl Sandburg
\end{quote}
\end{document}