# HG changeset patch
# User Jordi Gutiérrez Hermoso <jordigh@octave.org>
# Date 1463542536 14400
# Node ID d5ec0659b26b090c06b91743cb1278592c3c8d0f
# Parent  bd102ae06bc4c7ccbcdc25d5ce39f2f714b61eb9
write last section

diff --git a/talk/talk.tex b/talk/talk.tex
--- a/talk/talk.tex
+++ b/talk/talk.tex
@@ -318,12 +318,13 @@
 
 \begin{frame}{Computing the medcouple}
   \begin{overlayarea}{\textwidth}{8cm}
-    \only<1>{%
+    \only<1>{
       \begin{center}
         \pgfimage[height=2in]{img/naive/medc-computation-init.png}
       \end{center}
-      Split up $X$ into $X^+$ and $X^-$ along the median.}
-    \only<2>{%
+      Split up $X$ into $X^+$ and $X^-$ along the median.
+    }
+    \only<2>{
       \begin{center}
         \pgfimage[height=2in]{img/naive/medc-computation.png}
       \end{center}
@@ -331,19 +332,143 @@
       \[
       \frac{ (x_i - x_m) - (x_m - x_j)}{x_i - x_j},
       \quad x_i \in X^+, \quad x_j \in X^-
-      \]}
-    \only<3>{%
+      \]
+    }
+    \only<3>{
       \begin{center}
         \pgfimage[height=2in]{img/naive/medc-computation-done.png}
       \end{center}
-      The median of this matrix is the medcouple.}
+      The median of this matrix is the medcouple.
+    }
   \end{overlayarea}
 \end{frame}
 
+\begin{frame}
+  Problem: this algorithm is $O(n^2)$!!
+\end{frame}
+
 \section{Computation of the Medcouple}
 
 \begin{frame}
-  wtf
+  Now pure CS:
+  \pause
+  \begin{problem}
+    Find the median of a matrix with sorted rows and sorted columns.
+  \end{problem}
+\end{frame}
+
+\begin{frame}
+  \emph{Donald B. Johnson; Tetsuo Mizoguchi (May 1978). "Selecting The
+    Kth Element In X + Y And X1 + X2 +...+ Xm". SIAM Journal of
+    Computing 7 (2): 147-153. doi:10.1137/0207013.}
+  \pause
+  \begin{itemize}
+    \item Old paper, hard to read. But cool ideas!
+    \pause
+    \item Paper generalises to $n$-dimensional array with sorted slices
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Preliminaries}
+  Helper algorithms:
+  \pause
+  \begin{description}
+    \item[Selection Algorithm:] e.g. quickselect,
+    \texttt{nth\_element} in C++ or \texttt{partition} in numpy, $O(n)$ time
+    \pause
+    \item[Weighted Median:] binary search using
+    selection algorithm, $O(n)$ time.
+  \end{description}
+\end{frame}
+
+\begin{frame}
+  We now make two important observations
+\end{frame}
+
+\begin{frame}{Two observations}
+  Compare against whole matrix in $O(n)$ time
+  \begin{overlayarea}{\textwidth}{6cm}
+    \only<1>{
+      \begin{center}
+        \pgfimage[width=2in]{img/kth-pair/greater-than}
+      \end{center}
+      
+      Bottom-up.
+    }
+    \only<2>{
+      \begin{center}
+        \pgfimage[width=2in]{img/kth-pair/less-than}
+      \end{center}
+      
+      Top-down.
+    }    
+  \end{overlayarea}
+\end{frame}
+
+\begin{frame}{Two observations}
+  Compare against half the matrix in $O(1)$ time
+  \begin{center}
+    \pgfimage[width=2in]{img/kth-pair/middle-of-middle}
+  \end{center}
+\end{frame}
+
+\begin{frame}{Putting it together}
+  Iteratively, we have bounds for the global median
+  \begin{center}
+    \pgfimage[width=2in]{img/kth-pair/row-medians}
+  \end{center}
+\end{frame}
+
+\begin{frame}{Putting it together}
+  If we align the row medians...
+  \begin{center}
+    \pgfimage[width=2in]{img/kth-pair/row-medians-aligned}
+  \end{center}
+\end{frame}
+
+\begin{frame}{Putting it together}
+  With the weighted median (in $O(n)$ time), we compare to at least half the
+  remaining entries, discarding at least $1/4$.
+  \begin{center}
+    \pgfimage[width=2in]{img/kth-pair/row-medians-compared}
+  \end{center}
+\end{frame}
+
+\begin{frame}
+  So, final algorithm!
+\end{frame}
+
+\begin{frame}{Grand finale}
+  Procedure (serves one medcouple)
+
+  \begin{enumerate}
+    \item Compute ingredients for medcouple matrix: $O(n \log n)$
+    \pause
+    \begin{enumerate}[(A)]
+      \item \label{loop} Compute $t = \text{median of row medians}$: $O(n)$
+      \pause
+      \item \label{compare} Compare $t$ to the whole matrix: $O(n)$
+      \pause
+      \item Found the median? Found the medcouple! DONE.
+      \pause
+      \item \label{compare} Use comparison from \eqref{compare} to
+      throw out entries.
+      \pause
+      \item More than $n$ entries remaining? LOOP TO \eqref{loop}.
+    \end{enumerate}
+    \pause
+    \item Use selection algorithm on remaining entries: $O(n)$.
+  \end{enumerate}
+  \pause
+
+  Step \eqref{compare} throws out at least $1/4$ of all entries, so
+  the whole algorithm is $O(n \log n)$.
+\end{frame}
+
+\begin{frame}
+  \begin{center}
+    \LARGE{Questions?}
+  \end{center}
 \end{frame}
 
 \end{document}
\ No newline at end of file