\toclesssection{Divide and Conquer}

\toclesssubsection{Concept}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Introduction}
  \textbf{Concept:}
  \begin{itemize}
    \item<2->
      {\color{MainA}Divide} the problem into smaller subproblems
    \item<3->
      {\color{MainA}Conquer} the subproblems through recursive solving.\\
      If subproblems are small enough solve them directly
    \item<4->
      {\color{MainA}Connect} all subsolutions to solve the overall problem
    \item<5->
      {\color{MainA}Recursive} application of the algorithm on smaller
      subproblems
    \item<6->
      {\color{MainA}Direct} solving of small subproblems
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\subsection{Maximum Subtotal}

\begin{frame}{Divide and Conquer}{Maximum Subtotal}
  \textbf{Input:}
  \begin{itemize}
    \item<2->
      Sequence {\color{MainA}$X$} of {\color{MainA}$n$} integers
  \end{itemize}
  \textbf{Output:}
  \begin{itemize}
    \item<3->
      Maximum sum of an uninterrupted subsequence of
      {\color{MainA}$X$} and its index boundary
  \end{itemize}
  \vspace{-1em}
  \onslide<4->
  \begin{table}[!t]
    \caption{input values}
    \begin{tabular}{c|c|c|c|c|c|c|c|c|c|c}
      Index & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
      \midrule
      Value & 31 & -41 & 59 & 26 & -53 & 58 & 97 & -93 & -23 & 84
    \end{tabular}
    \label{tab:divide_and_conquer:max_subtotal_example_values}
  \end{table}
  \vspace{1em}
  %TODO: Hand-Drawings here (Free space) or no free space?
  \textbf{Output:} Sum: 187, Start: 2, End: 6
\end{frame}

%-------------------------------------------------------------------------------

%% \begin{frame}{Divide and Conquer}{Maximum Subtotal}
%%   \begin{example}[Maximum Subtotal]
%%     \vspace{-1em}
%%     \begin{table}[!t]
%%       \caption{Input values}
%%       \begin{tabular}{c|c|c|c|c|c|c|c|c|c|c}
%%         Index & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
%%         \midrule
%%         Value & 31 & -41 & 59 & 26 & -53 & 58 & 97 & -93 & -23 & 84
%%       \end{tabular}
%%       \label{tab:divide_and_conquer:max_subtotal_example_values}
%%     \end{table}
%%     \vspace{6em}
%%     %TODO: Hand-Drawings here (Free space) or no free space?
%%     \textbf{Output:} Sum: 187, Start: 2, End: 6
%%   \end{example}
%% \end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal}
  \textbf{Idea:}
  \begin{figure}
    \begin{adjustbox}{width=\linewidth}
      \input{Images/DivideAndConquer/MaxSubTotal_idea.tikz}
    \end{adjustbox}
    \label{fig:divide_and_conquer:max_sub_total_divide}
  \end{figure}
  \vspace{-1.5em}
  \begin{itemize}
    \item<2->
      Solve the left / right half of the problem {\color{MainA}recursively}
    \item<3->
      Combine both solutions into an overall solution
    \item<4->
      The maximum is located in the {\color{MainA}left~half~($A$)}
      or the {\color{MainA}right~half~($B$)}
    \item<5->
      The maximum interval can {\color{MainA} overlap with the border ($C$)}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal}
  \textbf{Principle:}
  \begin{figure}[!h]
    \begin{adjustbox}{width=\linewidth}
      \input{Images/DivideAndConquer/MaxSubTotal_Divide.tikz}
    \end{adjustbox}
    \label{fig:divide_and_conquer:max_sub_total_divide2}
  \end{figure}
  \vspace{-1.5em}
  \begin{itemize}
    \item<2->
      Small problems are solved directly:
      {\color{MainA}$n = 1 \Rightarrow \max = X[0]$}
    \item<3->
      Big problems are decomposed into two subproblems and solved recursively.
      Subsolutions {\color{MainA}$A$} and {\color{MainA}$B$}
      are returned.
    \item<4->
      To solve {\color{MainA}$C$} we have to calculate
      {\color{MainA}rmax} and {\color{MainA}lmax}
    \item<5->
      The overall solution is the maximum of {\color{MainA}$A$},
      {\color{MainA}$B$} and {\color{MainA}$C$}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\codeslide{python}{
\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={maxSubArray,lmax,rmax},
    emphstyle=\color{blue},
    breaklines=false
  ]{Code/DivideAndConquer/MaxSubTotal_DivideAndConquer.py}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={maxSubArray},
    emphstyle=\color{blue}
  ]{Code/DivideAndConquer/MaxSubTotal_SecondTrivialCase.py}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={maxSubArray},
    emphstyle=\color{blue}
  ]{Code/DivideAndConquer/MaxSubTotal_Max.py}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={maxSubArray},
    emphstyle=\color{blue}
  ]{Code/DivideAndConquer/MaxSubTotal_Max2.py}
\end{frame}
%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={lmax},
    emphstyle=\color{blue}
  ]{Code/DivideAndConquer/MaxSubTotal_LMax.py}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    escapechar={@},
    emph={rmax},
    emphstyle=\color{blue}
  ]{Code/DivideAndConquer/MaxSubTotal_RMax.py}
\end{frame}
}

%TODO: Implement for Java / C++

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal}
  \begin{table}
    \caption{\textit{lmax} example}
    \label{fig:divide_and_conquer:lmax_example}
    \begin{tabular}{c|cccccc}
      index & $i$ & $i+1$ & $\cdots$ & $\cdots$ & $j-1$ & $j$\\
      %\midrule
      $X$ & 58 & -53 & 26 & 59 & -41 & 31\\
      %\midrule
       {\color{MainA}$sum$} & 58 & 5 & 31 & 90 & 49 & 80\\
      {\color{MainA}$lmax$} & 58 & 58 & 58 & 90 & 90 & 90\\
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item<2->
      The {\color{MainA}$sum$} and {\color{MainA}$lmax$} are initialized with $X[i]$
    \item<3->
      We iterate over {\color{MainA}$X$} from {\color{MainA}$i+1$} to {\color{MainA}$j$} and update {\color{MainA}$sum$}
    \item<4->
      If {\color{MainA}$sum > lmax$}, then {\color{MainA}$lmax$}
      gets updated
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal}
  \begin{tabular}{l}
\onslide<1>{\rlap{\includegraphics[width=1\textwidth]{Images/DivideAndConquer/maxsubarray-o1.pdf}}}%
\onslide<2>{\rlap{\includegraphics[width=1\textwidth]{Images/DivideAndConquer/maxsubarray-o2.pdf}}}%
\onslide<3>{\rlap{\includegraphics[width=1\textwidth]{Images/DivideAndConquer/maxsubarray-o3.pdf}}}%
\onslide<4>{\rlap{\includegraphics[width=1\textwidth]{Images/DivideAndConquer/maxsubarray-o4.pdf}}}%
\onslide<5->{\rlap{\includegraphics[width=1\textwidth]{Images/DivideAndConquer/maxsubarray-o5.pdf}}}%
  \end{tabular}
\end{frame}

%-------------------------------------------------------------------------------

% \begin{frame}{Divide and Conquer}{Maximum Subtotal}
%   \begin{figure}
%     \begin{adjustbox}{width=\linewidth}
%       \input{Images/DivideAndConquer/MaxSubTotal_Example.tikz}
%     \end{adjustbox}
%     \caption{\textit{maxSubArray} with $X = [-3, 9, -4, 7]$}
%     \label{fig:divide_and_conquer:max_sub_array_example}
%   \end{figure}
% \end{frame}

%-------------------------------------------------------------------------------

\codeslide{python}{
\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    breaklines=false,
    escapechar={@},
    emph={maxSubArray,lmax,rmax},
    emphstyle=\color{blue}
  ]{Code/DivideAndConquer/MaxSubTotal_Runtime.py}
\end{frame}
}

%TODO: Implement for Java / C++

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Number of steps $T(n)$}
  \textbf{Recursion equation:} 
  \begin{displaymath}
    T(n) = \begin{cases}
      \hfill \underbrace{\Theta(1)}_\text{trivial case} & n = 1\\
      \underbrace{2 \cdot T\left(\frac{n}{2}\right)}_\text{
        solving of subproblems
      } + \underbrace{
        \Theta(n)
        \vphantom{\left(\frac{n}{2}\right)}
      }_\text{combination of solutions} & n > 1
    \end{cases}
  \end{displaymath}
    \begin{itemize}
    \item<2->
      There exist two constants {\color{MainA}$a$} and {\color{MainA}$b$} with:
      \begin{displaymath}
        T(n) \leq \begin{cases}
          \hfill {\color{MainA}a} & n = 1\\
          2 \cdot T\left(\frac{n}{2}\right) + {\color{MainA}b} \cdot n & n > 1
        \end{cases}
      \end{displaymath}
    \item<3->
      We define {\color{MainA}$c := \max(a,b)$}:
      \begin{displaymath}
        T(n) \leq \begin{cases}
          \hfill {\color{MainA}c} & n = 1\\
          2 \cdot T\left(\frac{n}{2}\right) + {\color{MainA}c} \cdot n & n > 1
        \end{cases}
      \end{displaymath}
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

%% \begin{frame}{Divide and Conquer}{Maximum Subtotal - Number of steps $T(n)$}
%%   \begin{itemize}
%%     \item
%%       There exist two constants $a$ and $b$ with:
%%       \begin{displaymath}
%%         T(n) \leq \begin{cases}
%%           \hfill a & n = 1\\
%%           2 \cdot T\left(\frac{n}{2}\right) + b \cdot n & n > 1
%%         \end{cases}
%%       \end{displaymath}
%%     \item
%%       We define $c := \max(a,b)$:
%%       \begin{displaymath}
%%         T(n) \leq \begin{cases}
%%           \hfill c & n = 1\\
%%           2 \cdot T\left(\frac{n}{2}\right) + c \cdot n & n > 1
%%         \end{cases}
%%       \end{displaymath}
%%   \end{itemize}
%% \end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Illustration of $T(n)$}
  \begin{figure}
    \begin{adjustbox}{width=\linewidth}
      \input{Images/DivideAndConquer/MaxSubTotal_Runtime.tikz}
    \end{adjustbox}
    \caption{illustration of the runtime}
    \label{fig:divide_and_conquer:max_sub_array_runtime}
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Illustration of $T(n)$}
  \begin{figure}
    \begin{adjustbox}{width=\linewidth}
      \input{Images/DivideAndConquer/MaxSubTotal_Runtime_Tree.tikz}
    \end{adjustbox}
    \caption{recursion tree method}
    \label{fig:divide_and_conquer:max_sub_array_runtime_tree}
  \end{figure}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Illustration of $T(n)$}
  \textbf{Depth:}
  \begin{itemize}
    \item<2->
      Top level with depth {\color{MainA}$i = 0$}
    \item<3->
      Lowest level with {\color{MainA}$2^i = n$} elements
      \begin{displaymath}
        {\color{MainA}\Rightarrow i = \log_2 n}
      \end{displaymath}
  \end{itemize}
  \onslide<4->
  \textbf{Runtime:}
  \begin{itemize}
    \item<5->
      A total of {\color{MainA}$\log_2 n + 1$} levels costing
      {\color{MainA}$c \cdot n$} each\\
      \color{gray}
      The costs of merging the solutions and solving the trivial
      problems are the same in this case
  \end{itemize}
  \onslide<6->
  \begin{displaymath}
    {\color{MainA}
    T(n) = c \cdot n \log_2 n + c \cdot n \in \Theta(n\,\log n)}
  \end{displaymath}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal - Summary}
  \textbf{Summary:}
  \begin{itemize}
    \item<2->
      Direct solution is slow with {\color{MainA}$\mathcal{O}(n^3)$}
    \item<3->
      Better solution with incremental update of sum was
      {\color{MainA}$\mathcal{O}(n^2)$}
    \item<4->
      Divide and conquer approach results in
      {\color{MainA}$\mathcal{O}(n\,\log n)$}
    \item<5->
      There is an approach running in {\color{MainA}$\mathcal{O}(n)$},
      under the assumption that all subtotals are positive
  \end{itemize}
\end{frame}

%-------------------------------------------------------------------------------

\begin{frame}{Divide and Conquer}{Maximum Subtotal}
  \begin{figure}
    \begin{adjustbox}{width=\linewidth}
      \input{Images/DivideAndConquer/MaxSubTotal_LinearRuntime.tikz}
    \end{adjustbox}
    \caption{scanning the array in linear time}
    \label{fig:divide_and_conquer:max_sub_total_linear}
  \end{figure}
\end{frame}

\codeslide{python}{
\begin{frame}{Divide and Conquer}{Maximum Subtotal - Python}
  \vspace{-0.5em}
  \lstinputlisting[
    language=Python,
    basicstyle=\small,
    tabsize=4,
    style={python-idle-code},
    breaklines=false,
    escapechar={@},
    emph={maxSubArray},
    emphstyle=\color{blue}
  ]{Code/DivideAndConquer/MaxSubTotal_LinearRuntime.py}
\end{frame}
}

%TODO: Implement for Java / C++
