
\begin{frame}
\frametitle{Lecture 16: Divide and Conquer Algorithms and Recurrences}

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$ ? }

\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 of Mergesort}
\end{frame}


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


\bigskip

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

\medskip
{\small \color{red}
Let $M(n_1,n_2)$ be the number of comparisons that algoirthm Merge does
in line 6.  The most occurs when $A[n_1-1]$ and $B[n_2-1]$ are compared.
This is $n1+n2-1$ comparisons.  Hence 
$$ M(n_1,n_2) \le n_1+n_2-1 $$
}
\end{frame}

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

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

{\small \color{red}
Let $C(n)$ be the number of comparisons that Mergesort does. \\
Line 1 says $C(1) = 0$.
The two recursive calls in lines 9 and 10 do $C(n_1)+C(n_2)$ comparisons.
The Merge does at most $n_1+n_2-1$ comparisons hence
$$
C(n) \le C(n_1) + C(n_2) + n_1 + n_2 - 1.
$$
For simplicity, we will do the analysis for $n = 2^k$ for some $k \ge 0$.
This assumption means $k= \log_2 n$ and $n_1 = n_2 = n/2$ and
$$
C(n) \le C(n/2) + C(n/2) + n/2 + n/2 - 1 = 2 C(n/2) + n-1.
$$
}

\end{frame}


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

Solving $C(n) \le 2 C(n/2) + n-1$ with $C(1) = 0$ assuming $n=2^k$.

{\color{red}
\begin{eqnarray*}
C(n) &\le& 2 \,C(n/2) + n-1 \\
2\,C(n/2) &\le& 2 [ 2 \,C(n/4) + (n/2-1) ] = 4 \,C(n/4) + n-2 \\
4\,C(n/4) &\le& 4 [ 2 \,C(n/8) + (n/4-1) ] = 8 \,C(n/8) + n-4  \\
...     &\le& \dots \\
\frac{n}{4} C(4) & \le & \frac{n}{4} [2 \,C(2) + (4-1) ] = \frac{n}{2} \,C(2) + n - \frac{n}{4} \\
\frac{n}{2} C(2) & \le & \frac{n}{2} \left [2 \,C(1) + (2-1) \right ] = n \,C(1) + n - \frac{n}{2} \\
n \,C(1)  & = & 0 \\
\end{eqnarray*}
%
Adding these inequalities and cancelling equal terms we have
%
\begin{eqnarray*}
C(n) & \le & (n-1) + (n-2) + (n-4) + \dots + (n-n/4) + (n-n/2) + 0 \\
     & = & \sum_{i=0}^{k-1} (n-2^i) 
      = \sum_{i=0}^{k-1} n - \sum_{i=0}^{k-1} 2^i \\
     & = & n k - (2^k - 1) 
      = n \log_2 n - n + 1
\end{eqnarray*}
}

\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}

{\color{red} \small
Let $f(n)$ be the number of operations to solve the problem using the divide-and-conquer
algorithm and 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 assume $f(1)=c$ for some constant $c \ge 0$.
}
%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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\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$ 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}
%
%{\color{red} \small
%
%{\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}

Example.  Adding an array of numbers.

\medskip

{\small \input{add} }

\medskip

{ \color{red}
Let $a_n$ be the number of additions in line 9. For simplicity
assume $n=2^k$ so $n_1 = n_2 = n/2$.  For $n=1$ we have $a_1 = 0$.  For $n>1$ we have 
\begin{eqnarray*}
a_n &=& a_{n_1} + a_{n_2} + 1 = 2 a_{n/2} + 1 \\
2 a_{n/2} &=& 2^2 a_{n/2^2} + 2 \\
2^2 a_{n/4} &=& 2^3 a_{n/2^3} + 2^2 \\
\dots \\            
2^{k-1} a_2 &=& 2^k a_1 +2^{k-1} = 2^{k-1}.
\end{eqnarray*}
Hence $a_n = 1+2+2^2+\dots+2^{k-1} = 2^k-1 = n-1$.
}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{ Maple examples using the rsolve command. }

\input{rsolve}
\end{frame}


\end{document}
