
\begin{frame}
\frametitle{Lecture 16: Divide and Conquer Algorithms and Recurrences }
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Please use the notes on Canvas not 10.6 Grimaldi.

\vspace{3cm}
{ \bf What is the fastest algorithm for sorting an array of $n$ numbers ? } \\
{ \bf What is the fastest algorithm to multiply two polynomials of degree $n$ ? }

\vspace{2cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Sorting Algorithms}

Suppose we want to sort an $A$ of $n$ integers e.g.

\bigskip

\begin{center}
$A$ = 
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 9 & 3 & 11 & 2 & 6 & 13 & 5 \\ \hline 
\end{tabular}
\end{center}

\bigskip

To compare sorting algorithms, by tradition, we count the number
of comparisons they do.  Bubblesort does exactly $\color{blue} n(n-1)/2$ comparisons.
Mergesort does at most $\color{blue} n \log_2 n - n + 1$ comparisons.
Below is a table for various values of $n$ comparing the number 
of comparisons of these two algorithms.

%
\begin{center}
\begin{tabular}{|l|l|c|c|c|c|c|c|} \hline
           & $n$                   & 4 & 16  & 64    & 1024   & $10^6$ \\ \hline
Bubblesort & $n(n-1)/2$            & 6 & 120 & 2016  & 523776 & approx $5 \times 10^{11}$ \\
Mergesort  & $n \log_2 n - n + 1$  & 5 & 49  &  321  &  9217  & approx $20 \times 10^6$ \\ \hline
\end{tabular}
\end{center}

\bigskip
For $n=10^6$ Mergesort does a factor of over $25,000$ fewer comparisons! \\
{\bf Demo Mergesort}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}


\begin{figure}[ht]
{\small \input{merge} }
\caption{C code for merging two sorted arrays A and B into the array C}
\end{figure}

\vspace{6cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{The Mergesort Algorithm}

\begin{figure}[H]
{\small \input{mergesort} }
\end{figure}

\vspace*{3cm}

% Let C(n) be the number of comparisons that Mergesort does
% C(1) = 0; line 1
% C(n) = C(m) + C(n-m) + M(m,n-m)
% Assume n = 2^k for simplicity so m = n/2
% C(n) = C(n/2) + C(n/2) + M(n/2,n/2)
% C(n) <= 2 C(n/2) + n-1

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

Solving $C(n) \le 2 C(n/2) + n-1$ with $C(1) = 0$.
\vspace{10cm}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Divide and Conquer Algorithms}

Suppose we are given a problem of size $n$.

\begin{itemize}
\item[S1:] {\dblue Divide the problem into $a \ge 2$ subproblems of approximately the same size, say size $b$.}
          Algorithm Mergesort divided $A$ into $a=2$ subproblems of size $n_1=n/2$ and $n_2=n-n_1$.
\item[S2:] {\dblue Solve the subproblems recursively using the same ``divide-and-conquer'' approach.} \\
\item[S3:] {\dblue Combine the results from the subproblems to obtain the final solution.} \\
          Algorithm Mergesort merges two sorted arrays of size $n_1$ and $n_2$ into
          one sorted array of size $n$.
\end{itemize}

\vspace*{3cm}

%\noindent
%Let $f(n)$ be the number of operations to solve the problem using the divide-and-conquer
%algorithm and we let $h(n)$ be the number of operations in steps 1 and 3.
%To make our analysis easier, we will assume $n = b^k$ which means we can always divide $n$
%exactly into $b$ sub-problems of size $n/b$.
%Then we have a recurrence for $f(n)$ of the form 
%\begin{equation}
%\label{DivConRec}
%   f(n)  =  a f(n/b) + h(n)  ~~{\rm for}~n>1.
%\end{equation}
%For $n=1$ we may assume the time to solve the problem is a constant $c \ge 0$
%so that $f(1)=c$.  In our Add example we have $a=2$, $b=2$, $c=0$ and $h(n)=1$
%so that the recurrence is $f(n) = 2 f(n/2) + 1$.
%Theorem 10.1 below solves recurrence (\ref{DivConRec}) for the case $h(n) = d$ where $d$ is a constant.
%Our Theorem 10.1 generalizes slightly Theorem 10.1 in the Grimaldi text.
%

\end{frame}


%
% Omit the general formula and do the Add example instead.
% Demo Maple's rsolve command and summation command.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%
%\begin{theorem}[ 10.1 ]
%{\bf Theorem 10.1} \ Let $a$ and $b$ be positive integers with $b \ge 2$.
%Let $c$ and $d$ be positive real numbers.
%Let $n=b^k$ for $k \ge 0$ and let $f : \ZZ^+ \rightarrow \RR$. \\
%If $\color{blue} f(1)=c$ and 
%$$\color{blue} f(n) = a f(n/b) + d \quad {\rm for}~ n>1$$
%then
%\begin{itemize}
%\item[(1)] $f(n) = d \log_b n + c$ \ for $a=1$.
%\item[(2)] $\displaystyle f(n) = d \frac{a n^{\log_b a}-1}{a-1} + c n^{\log_b a}$ \ for $a\ge 2$.
%\item[(3)] $f(n) = \frac{n-1}{a-1} d + n c$ \ for $a \ge 2$ and $b=a$.
%\end{itemize}
%\end{theorem}
%
%\bigskip
%Note our Theorem 10.1 generalizes slightly Theorem 10.1 in the Grimaldi text.
%
%\end{frame}
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%
%Proof. \ $f(n) = a f(n/b) + d$
%
%\vspace{12cm}

%%{\bf Proof:} \  For $k \ge 1$ we expand the recurrence to obtain the following equations
%%\begin{eqnarray*}
%%f(n) &=& a f(n/b) + d \\
%%af(n/b) &=& a( af(n/b^2)+d ) = a^2 f(n/b^2) + a d \\
%%a^2f(n/b^2) &=& a^2( af(n/b^3)+d) = a^3 f(n/b^3) + a^2 d \\
%%\vdots &\le& \vdots \\
%%a^{k-2} f(n/b^{k-2}) & = & a^{k-1} f(n/b^{k-2}) + a^{k-2} d \\
%%a^{k-1} f(n/b^{k-1}) & = & a^k f(n/b^k) + a^{k-1} d = a^k f(1) + a^{k-1} d \\
%%a^{k} f(1) & = & a^k c \\
%%\end{eqnarray*}
%%Adding these equations and cancelling equal terms we have
%%\begin{eqnarray*}
%%f(n) &=& a^k f(1) + (d + ad + a^2 d + \dots + a^{k-1} d) \\
%%     &=& a^k c + (1+a+a^2 + \dots + a^{k-1}) d.
%%\end{eqnarray*}
%%Using $n=b^k$ so that $k=\log_b n$, for $a=1$ we obtain
%%(1) $f(n) = c + k d = c + d \log_b n.$
%%To show (2) we 
%%use $\sum_{i=0}^{k-1} a^i = \frac{a^k-1}{a-1}$ and $a^k = a^{\log_b n} = n^{\log_b a}$ so that
%%$$
%%f(n) = a^k c + \frac{a^k-1}{a-1} d = c n^{\log_b a} + d \frac{n^{\log_b a}-1}{a-1}.
%%$$
%%For case (3) where $a=b$ we have $\log_b a = 1$ so $f(n) = c n + \frac{n-1}{a-1} d$.
%%This ends the proof.
%
%\end{frame}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%Additional space
%\vspace{12cm}
%
%\end{frame}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

Example.  Adding an array of numbers.

\medskip

{\small \input{add} }

\vspace{8cm}
% Let A(n) be the number of additions algorithm Add does in line 9.
% Assume n = 2^k for some k >= 0.
% A(1) = 0 from line 4
% 1 A(n) = 2 A(n/2) + 1 from lines 6, 8 and 9.
% 2 A(n/2) = 2( 2A(n/4)+1 ) = 2^2 A(n/2^2) + 2
% 2^2 A(n/2^2) = 2^2( 2A(n/8)+1 ) = 2^3 A(n/2^3) + 2^2
% ...
% 2^(k-1) A(2^1) = 2^(k-1) (2A(1)+1) = 2^k A(1) + 2^(k-1)
% 2^k A(1) = 0
% A(n) = 1 + 2 + 2^2 + ... + 2^(k-1) = 2^k-1 = n-1
%

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{ Solving recurrences using Maple's rsolve command. }

\input{rsolve}
\end{frame}

