From 67393f42f41ab92219deb549f711121c4dab845b Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Sun, 15 Dec 2019 10:34:58 +0700
Subject: [usth/ICT2.2] Object Oriented Programming

---
 usth/ICT2.2/midterm/slides/slides.tex | 734 ++++++++++++++++++++++++++++++++++
 1 file changed, 734 insertions(+)
 create mode 100644 usth/ICT2.2/midterm/slides/slides.tex

(limited to 'usth/ICT2.2/midterm/slides/slides.tex')

diff --git a/usth/ICT2.2/midterm/slides/slides.tex b/usth/ICT2.2/midterm/slides/slides.tex
new file mode 100644
index 0000000..b69cdff
--- /dev/null
+++ b/usth/ICT2.2/midterm/slides/slides.tex
@@ -0,0 +1,734 @@
+\documentclass[pdf]{beamer}
+\usepackage[english,vietnamese]{babel}
+\usepackage{amsmath}
+\usepackage{booktabs}
+\usepackage{colortbl}
+\usepackage{graphicx}
+\usepackage{hyperref}
+\usepackage{lmodern}
+\usepackage{forest}
+
+\mode<presentation>{}
+\usetheme[hideothersubsections]{Hannover}
+\usefonttheme[onlymath]{serif}
+\usebackgroundtemplate{
+  \includegraphics[width=\paperwidth,height=\paperheight]{USTH.jpg}}
+\beamerdefaultoverlayspecification{<+->}
+
+\title[Sort \& Search]{Sorting and Searching}
+\author[Group 11]{Nguyễn Công Thành---BI9-210\\
+                  Nguyễn Gia Phong---BI9-184\\
+                  Nguyễn Văn Tùng---BI9-229\\
+                  Trần Minh Vương---BI9-239\\
+                  Trần Hồng Minh---BI8-114}
+\institute{University of Science and Technology of Hà Nội}
+\date{\selectlanguage{english}\today}
+
+\begin{document}
+\frame{\titlepage}
+\begin{frame}{Contents}
+  \tableofcontents
+\end{frame}
+
+\section{Introduction}
+\begin{frame}{Introduction}\Large
+  \begin{itemize}
+    \item Sorting \& Searching are \emph{important}
+    \item Object-Oriented Programming
+    \item Implementation in Java
+    \item Generic Programming
+  \end{itemize}
+\end{frame}
+
+\section{Searching}
+\begin{frame}[fragile]{Searching}\Large
+  Given a value $x$, return the [zero-based] index of $x$ in the array,
+  if such $x$ exists.  Otherwise, return \verb|NOT_FOUND| (-1).
+\end{frame}
+
+\subsection{Linear Search}
+\begin{frame}[fragile]{Linear Search}\Large
+  \begin{itemize}
+    \item Checks sequentially till
+      \begin{itemize}\Large
+        \item match found
+        \item whole list searched
+      \end{itemize}
+    \item Linear time complexity
+    \item \verb|java.util.List.indexOf|
+    \item Example: Search for number 7
+      \begin{center}
+        \only<1-5>{\begin{tabular}{|c|c|c|c|c|}
+          \hline 4 & 20 & 6 & 9\\\hline
+        \end{tabular}}%
+        \only<6>{\begin{tabular}{|c|c|c|c|c|}
+          \hline \cellcolor{yellow}4 & 20 & 6 & 9\\\hline
+        \end{tabular}}%
+        \only<7>{\begin{tabular}{|c|c|c|c|c|}
+          \hline 4 & \cellcolor{yellow}20 & 6 & 9\\\hline
+        \end{tabular}}%
+        \only<8>{\begin{tabular}{|c|c|c|c|c|}
+          \hline 4 & 20 & \cellcolor{yellow}6 & 9\\\hline
+        \end{tabular}}%
+        \only<9>{\begin{tabular}{|c|c|c|c|c|}
+          \hline 4 & 20 & 6 & \cellcolor{yellow}9\\\hline
+        \end{tabular}}
+      \end{center}
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Implementation}
+\begin{verbatim}
+import java.util.List;
+
+public class Search
+{
+  public static final int NOT_FOUND = -1;
+
+  public static linear(List l, Object o)
+  {
+    for (int i = 0; i < l.size(); ++i)
+      if (o == null ? l.get(i) == null
+                    : o.equals(l.get(i)))
+        return i;
+    return NOT_FOUND;
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\subsection{Binary Search}
+\begin{frame}[fragile]{Binary Search}\Large
+  \begin{itemize}
+    \item For sorted arrays only
+    \item Repeat halving interval cannot have $x$ till
+      \begin{itemize}\Large
+        \item match found
+        \item invalid interval
+      \end{itemize}
+    \item Logarithmic time complexity
+    \item \verb|java.util.Collections.binarySearch|
+    \item Example: Search for number 7
+      \begin{center}
+        \only<1-6>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
+          \hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & $\emptyset$\\\hline
+        \end{tabular}}%
+        \only<7>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
+          \hline \cellcolor{red}0 & 1 & 2 & 3 & 4 & \cellcolor{green}5
+          & 6 & 7 & 8 & 9 & \cellcolor{blue}$\emptyset$\\\hline
+        \end{tabular}}%
+        \only<8>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
+          \hline 0 & 1 & 2 & 3 & 4 & 5 & \cellcolor{red}6 & 7
+          & \cellcolor{green}8 & 9 & \cellcolor{blue}$\emptyset$\\\hline
+        \end{tabular}}%
+        \only<9>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
+          \hline 0 & 1 & 2 & 3 & 4 & 5 & \cellcolor{yellow}6 & \cellcolor{blue}7
+          & 8 & 9 & $\emptyset$\\\hline
+        \end{tabular}}%
+        \only<10>{\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
+          \hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & \cellcolor{gray}7
+          & 8 & 9 & $\emptyset$\\\hline
+        \end{tabular}}
+      \end{center}
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Implementation}
+\begin{verbatim}
+public class Search
+{
+  private static <T> int binary(
+    List<? extends Comparable<? super T>> list,
+    T key, int low, int high)
+  {
+    if (high < low)
+      return NOT_FOUND;
+    var mid = (low + high) / 2;
+    var cmp = list.get(mid).compareTo(key);
+    if (cmp < 0)
+      return binary(list, key, mid + 1, high);
+    if (cmp > 0)
+      return binary(list, key, low, mid - 1);
+    return mid;
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{Wrapper}
+\begin{verbatim}
+public class Search
+{
+  public static <T> int binary(
+    List<? extends Comparable<? super T>> list,
+    T key)
+  {
+    return binary(list, key, 0, list.size());
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\section{Sorting}
+\begin{frame}{Sorting}\Large
+  Given an array of $n$ values, arrange the values into ascending order.
+\end{frame}
+
+\subsection{Selection Sort}
+\begin{frame}{Selection Sort}\Large
+  \begin{itemize}
+    \item Iterate through every position,\\
+      select the minimum from there to array's end
+    \item Quadratic time complexity
+    \item Example:
+      \only<1-2>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 6 & 9 & 4 & 2 & 0\\\hline
+      \end{tabular}}%
+      \only<3>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 6 & 9 & 4 & 2 & \cellcolor{yellow}0\\\hline
+      \end{tabular}}%
+      \only<4>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{gray}0 & 9 & 4 & \cellcolor{yellow}2 & 6\\\hline
+      \end{tabular}}%
+      \only<5>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{gray}0 & \cellcolor{gray}2 &
+        \cellcolor{yellow}4 & 9 & 6\\\hline
+      \end{tabular}}%
+      \only<6>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{gray}0 & \cellcolor{gray}2 &
+        \cellcolor{gray}4 & 9 & \cellcolor{yellow}6\\\hline
+      \end{tabular}}%
+      \only<7>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{gray}0 & \cellcolor{gray}2 &
+        \cellcolor{gray}4 & \cellcolor{gray}6 & \cellcolor{yellow}9\\\hline
+      \end{tabular}}%
+      \only<8>{\begin{tabular}{|c|c|c|c|c|}
+        \hline\rowcolor{gray} 0 & 2 & 4 & 6 & 9\\\hline
+      \end{tabular}}
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile,label=selimpl]{Implementation}
+\begin{verbatim}
+import static java.util.Collections.swap;
+
+public class Sort
+{
+  public static <T extends Comparable<? super T>>
+  void selection(List<T> list)
+  {
+    int i, j, m, n = list.size();
+    for (i = 0; i < n; ++i)
+      {
+        for (m = j = i; j < n; ++j)
+          if (list.get(j).compareTo(list.get(m)) < 0)
+            m = j;
+        swap(list, i, m);
+      }
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\subsection{Bubble Sort}
+\begin{frame}{Bubble Sort}\Large
+  \begin{itemize}
+    \item Repeatedly iterate through the array,\\
+      swap adjacent elements in wrong order
+    \item Quadratic time complexity
+    \item Example:
+      \only<1-2>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 6 & 9 & 4 & 2 & 0\\\hline
+      \end{tabular}}%
+      \only<3>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{magenta}6 & \cellcolor{yellow}9 & 4 & 2 & 0\\\hline
+      \end{tabular}}%
+      \only<4>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 6 & \cellcolor{magenta}9 & \cellcolor{yellow}4 & 2 & 0\\\hline
+      \end{tabular}}%
+      \only<5>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 6 & 4 & \cellcolor{magenta}9 & \cellcolor{yellow}2 & 0\\\hline
+      \end{tabular}}%
+      \only<6>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 6 & 4 & 2 & \cellcolor{magenta}9 & \cellcolor{yellow}0\\\hline
+      \end{tabular}}%
+      \only<7>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{magenta}6 & \cellcolor{yellow}4
+        & 2 & 0 & \cellcolor{gray}9\\\hline
+      \end{tabular}}%
+      \only<8>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 4 & \cellcolor{magenta}6 & \cellcolor{yellow}2
+        & 0 & \cellcolor{gray}9\\\hline
+      \end{tabular}}%
+      \only<9>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 4 & 2 & \cellcolor{magenta}6 & \cellcolor{yellow}0
+        & \cellcolor{gray}9\\\hline
+      \end{tabular}}%
+      \only<10>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{magenta}4 & \cellcolor{yellow}2 & 0
+        & \cellcolor{gray}6 & \cellcolor{gray}9\\\hline
+      \end{tabular}}%
+      \only<11>{\begin{tabular}{|c|c|c|c|c|}
+        \hline 2 & \cellcolor{magenta}4 & \cellcolor{yellow}0
+        & \cellcolor{gray}6 & \cellcolor{gray}9\\\hline
+      \end{tabular}}%
+      \only<12>{\begin{tabular}{|c|c|c|c|c|}
+        \hline \cellcolor{magenta}2 & \cellcolor{yellow}0
+        & \cellcolor{gray}4 & \cellcolor{gray}6 & \cellcolor{gray}9\\\hline
+      \end{tabular}}%
+      \only<13>{\begin{tabular}{|c|c|c|c|c|}
+        \hline\rowcolor{gray} 0 & 2 & 4 & 6 & 9\\\hline
+      \end{tabular}}
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Implementation}
+\begin{verbatim}
+public class Sort
+{
+  public static <T extends Comparable<? super T>>
+  void bubble(List<T> list)
+  {
+    for (int n = list.size(), m = 0;
+         n > 1; n = m, m = 0)
+      for (int i = 1; i < n; ++i)
+        if (list.get(i).compareTo(list.get(i-1)) < 0)
+          swap(list, m = i, i - 1);
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}{Bubble v Selection: Dawn of Sort}\Large
+  \only<1>{
+    C. Thomas Wu (2010) claimed that
+    \begin{quote}
+      On average, we expect the bubble sort to finish sorting sooner than
+      the selection sort, \emph{because there will be more data movements for
+      the same number of comparisons}, and there is a test to exit the method
+      when the array gets sorted.
+    \end{quote}}
+  \only<2>{\includegraphics[width=\textwidth]{squint.jpg}}
+\end{frame}
+
+\begin{frame}{BvS: Time Complexity}
+  \begin{center}
+    \begin{tabular}{c c c c c}
+      \toprule
+      Case & \multicolumn{2}{c}{Selection Sort}
+           & \multicolumn{2}{c}{Bubble Sort}\\
+      \midrule
+      & Comparisons & Swaps & Comparisons & Swaps\\
+      Best & $\Omega(n^2)$ & $\Omega(n)$ & $\Omega(n)$ & $\Omega(n)$\\
+      Average & $\Theta(n^2)$ & $\Theta(n)$ & $\Theta(n^2)$ & $\Theta(n^2)$\\
+      Worst & $O(n^2)$ & $O(n)$ & $O(n^2)$ & $O(n^2)$\\
+      \bottomrule
+    \end{tabular}
+  \end{center}
+\end{frame}
+
+\begin{frame}{BvS: Average Case in Practice}
+  \begin{center}
+    \includegraphics[width=0.85\textwidth]{bubbleplot.jpg}
+  \end{center}
+\end{frame}
+
+\subsection{Heapsort}
+\begin{frame}{Heapsort}\Large
+  \begin{itemize}
+    \item Selection sort, but use heap for selection
+    \item Linearithmic time complexity
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Using PriorityQueue (Min-Heap)}
+\begin{verbatim}
+import java.util.PriorityQueue;
+
+public class Sort
+{
+  public static <T extends Comparable<? super T>>
+  void pq(List<T> list)
+  {
+    var q = new PriorityQueue<T>(list);
+    for (int i = 0; i < list.size(); ++i)
+      list.set(i, q.poll());
+  }
+}
+\end{verbatim}\pause
+
+But hey, there is also \verb|List.sort|!
+\end{frame}
+
+\begin{frame}{Binary Max-Heap}\Large
+  \begin{itemize}
+    \item Nearly complete binary tree
+    \item Parent $\ge$ Children $\Longrightarrow$ Root is max!
+    \item Example:
+      \begin{center}
+        \begin{forest}
+          for tree={circle,draw}
+          [9 [4 [0] [6]] [8 [3] [,phantom]]]
+        \end{forest}
+      \end{center}
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Linear Binary Max-Heap}\Large
+  \begin{itemize}
+    \item $length$ of inner representation
+    \item $size$ of heap ($0 \le size \le length$)
+    \item Index within $[0\,..\, size)$
+      \[\begin{array}{ll}
+        \mathrm{parent}(i) &= \left\lfloor\dfrac{i - 1}{2}\right\rfloor\\
+        \mathrm{left}(i) &= 2i + 1\\
+        \mathrm{right}(i) &= 2i + 2
+      \end{array}\]
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Heap Declaration}
+\begin{verbatim}
+public class Heap<T extends Comparable<? super T>>
+{
+  private List<T> list;
+  private int size;
+
+  public int getSize() { return size; }
+  public int getLength() { return list.size(); }
+  public T get(int i) { return list.get(i); }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{void Heap::heapify(int i)}
+\begin{verbatim}
+int right = i + 1 << 1;
+int left = right - 1;
+int largest = i;
+if (left < size
+    && get(left).compareTo(get(largest)) > 0)
+  largest = left;
+if (right < size
+    && get(right).compareTo(get(largest)) > 0)
+  largest = right;
+if (largest != i)
+  {
+    swap(list, i, largest);
+    heapify(largest);
+  }
+\end{verbatim}
+\end{frame}
+
+\begin{frame}{Heapification}\huge
+  \begin{center}
+    \only<1>{\begin{forest}
+      for tree={circle,draw}
+      [4,fill=yellow [9 [0] [6]] [8 [3] [,phantom]]]
+    \end{forest}}%
+    \only<2>{\begin{forest}
+      for tree={circle,draw}
+      [9 [4,fill=yellow [0] [6]] [8 [3] [,phantom]]]
+    \end{forest}}%
+    \only<3>{\begin{forest}
+      for tree={circle,draw}
+      [9 [6 [0] [4,fill=yellow]] [8 [3] [,phantom]]]
+    \end{forest}}
+  \end{center}
+\end{frame}
+
+\begin{frame}[fragile]{The Loop Invariant}\Large
+  For $i$ =$\lfloor n/2\rfloor - 1$ downto $0$, \verb|heapify(i)|:
+  \begin{itemize}
+    \item \textbf{Initialization}: For every array,
+      each node $\lfloor n/2\rfloor\,..\,n-1$ is trival max-heap (leaf).
+    \item \textbf{Maintenance}: If nodes $i+1\,..\,n-1$ are max-heaps,
+      after \verb|heapify(i)|, all nodes $i\,..\,n-1$ are max-heaps.
+    \item \textbf{Terminination}: After \verb|heapify(0)|,
+      the whole array is a max-heap.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Heap Constructor}
+\begin{verbatim}
+public class Heap<T extends Comparable<? super T>>
+{
+  public Heap(List<T> a)
+  {
+    list = a;
+    size = a.size();
+    for (int i = size >> 1; i-- > 0;)
+      heapify(i);
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{Maximum Selection}
+\begin{verbatim}
+public class Heap<T extends Comparable<? super T>>
+{
+  public T pop() throws RuntimeException
+  {
+    if (size < 1)
+      throw new RuntimeException("heap underflow");
+    swap(list, 0, --size);
+    heapify(0);
+    return get(size);
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{Heapsort Implementation}
+\begin{verbatim}
+public class Sort
+{
+  public static <T extends Comparable<? super T>>
+  void heap(List<T> list)
+  {
+    var heap = new Heap<T>(list);
+    for (int i = 1; i < list.size(); ++i)
+      heap.pop();
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}{Sorting a Heap}\huge
+  \begin{center}
+    \only<1>{\begin{forest}
+      for tree={circle,draw}
+      [9 [6 [0] [4]] [8 [3] [,phantom]]]\
+    \end{forest}}%
+    \only<2>{\begin{forest}
+      for tree={circle,draw}
+      [8 [6 [0] [4]] [3 [9,edge=dashed] [,phantom]]]
+    \end{forest}}%
+    \only<3>{\begin{forest}
+      for tree={circle,draw}
+      [6 [4 [0] [8,edge=dashed]] [3 [9,edge=dashed] [,phantom]]]
+    \end{forest}}%
+    \only<4>{\begin{forest}
+      for tree={circle,draw}
+      [4 [0 [6,edge=dashed] [8,edge=dashed]]
+         [3 [9,edge=dashed] [,phantom]]]
+    \end{forest}}%
+    \only<5>{\begin{forest}
+      for tree={circle,draw}
+      [3 [0 [6,edge=dashed] [8,edge=dashed]]
+         [4,edge=dashed [9,edge=dashed] [,phantom]]]
+    \end{forest}}%
+    \only<6>{\begin{forest}
+      for tree={circle,draw}
+      [0 [3,edge=dashed [6,edge=dashed] [8,edge=dashed]]
+         [4,edge=dashed [9,edge=dashed] [,phantom]]]
+    \end{forest}}%
+  \end{center}
+\end{frame}
+
+\section{Comparing}
+\begin{frame}[fragile]{Comparing}\Large
+  \begin{itemize}
+    \item $<$, $\le$, $=$, $\ge$, $>$ or $\ne$?
+    \item e.g. \verb|420 > 69|
+    \item But \verb|"420" < "69"|!
+    \item How do we sort any collection of data?
+  \end{itemize}
+\end{frame}
+
+\subsection{Comparable}
+\begin{frame}[fragile]{Comparable}\Large
+  \begin{itemize}
+    \item \emph{Natural} increasing order
+    \item Define \verb|int compareTo(T other)|
+    \item Negative: less than; Zero: equal;\\
+      Positve: greater than.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Example Element}
+\begin{verbatim}
+public class Person implements Comparable<Person>
+{
+  private String name;
+  private Integer age;
+  private Character gender;
+
+  public int compareTo(Person other)
+  {
+    return this.name.compareTo(other.name);
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{Example Element (misc.)}
+\begin{verbatim}
+public class Person implements Comparable<Person>
+{
+  public Person(String name, Integer age,
+                Character gender)
+  {
+    this.name = name;
+    this.age = age;
+    this.gender = gender;
+  }
+
+  public String toString()
+  {
+    return String.format("%s (%d%c)",
+                         name, age, gender);
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\againframe{selimpl}
+
+\begin{frame}[fragile]{Sorting People}
+\begin{verbatim}
+var list = java.util.Arrays.asList(
+  new Person("Mahathir Mohamad", 94, 'M'),
+  new Person("Elizabeth II", 93, 'F'),
+  new Person("Paul Biya", 86, 'M'),
+  new Person("Michel Aoun", 84, 'M'),
+  new Person("Mahmoud Abbas", 83, 'M'),
+  new Person("Francis", 82, 'M'));
+Sort.selection(list);
+list.forEach(System.out::println);
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{Sort by Name Output}\Large
+  \begin{quote}
+    Elizabeth II (93F)\\
+    Francis (82M)\\
+    Mahathir Mohamad (94M)\\
+    Mahmoud Abbas (83M)\\
+    Michel Aoun (84M)\\
+    Paul Biya (86M)
+  \end{quote}
+\end{frame}
+
+\subsection{Comparator}
+\begin{frame}[fragile]{Comparator}\Large
+  \begin{itemize}
+    \item How about reverse order?
+    \item Sort by another \emph{key}?
+    \item \verb|compareTo| (or any other) method\\
+      cannot be overriden without subclassing.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{java.util.Comparator}\Large
+  \begin{itemize}
+    \item Define \verb|int compare(T one, T another)|
+    \item Negative: less than; Zero: equal;\\
+      Positve: greater than.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Refactored Selection Sort}
+\begin{verbatim}
+public class Sort
+{
+  public static <T>
+  void selection(List<T> list,
+                 Comparator<T> comparator)
+  {
+    int i, j, m, n = list.size();
+    for (i = 0; i < n; ++i)
+      {
+        for (m = j = i; j < n; ++j)
+          if (comparator.compare(list.get(j),
+                                 list.get(m)) < 0)
+            m = j;
+        swap(list, i, m);
+      }
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{Exposing Attributes}
+\begin{verbatim}
+public class Person implements Comparable<Person>
+{
+  public String getName() { return name; }
+  public Integer getAge() { return age; }
+  public Character getGender() { return gender; }
+}
+\end{verbatim}
+\end{frame}
+
+\begin{frame}[fragile]{Sorting by Age}
+\begin{verbatim}
+Sort.heap(list, new Comparator<Person>()
+{
+  public int compare(Person a, Person b)
+  {
+    return a.getAge().compareTo(b.getAge());
+  }
+});
+list.forEach(System.out::println);
+\end{verbatim}
+\end{frame}
+
+\begin{frame}{Sorting by Age Output}\Large
+  \begin{quote}
+    Francis (82M)\\
+    Mahmoud Abbas (83M)\\
+    Michel Aoun (84M)\\
+    Paul Biya (86M)\\
+    Elizabeth II (93F)\\
+    Mahathir Mohamad (94M)
+  \end{quote}
+\end{frame}
+
+\begin{frame}[fragile]{Backward Compatibility}
+\begin{verbatim}
+public class Compare<T extends Comparable<? super T>>
+implements Comparator<T>
+{
+  public int compare(T a, T b)
+  {
+    return a.compareTo(b);
+  }
+}
+
+public class Sort
+{
+  public static <T extends Comparable<? super T>>
+  void selection(List<T> list)
+  {
+    selection(list, new Compare<T>());
+  }
+}
+\end{verbatim}
+\end{frame}
+
+\section{Conclusion}
+\begin{frame}{Conclusion}\Large
+  Though the topic is more algorithmic than OOP:
+  \begin{itemize}
+    \item \textbf{Encapsulation}: Intuitive interface and concise code,
+      e.g. binary search, heap.
+    \item \textbf{Polymorphism}: Generic, convenient libraries,
+      thus more \emph{code reuse} and more effective development.
+    \item \textbf{Inheritance}: Extend objects' functionalities,
+      hence even more generalization.
+    \item However, shoving every self-contained function into a class
+      is rather redundant.
+  \end{itemize}
+\end{frame}
+
+\begin{frame}{Copying}\Large
+  \begin{itemize}
+    \item For the list of references, see our report.
+    \item The report also contains more explainations and examples.
+    \item The documents as well as Java source files are licensed under
+      \href{https://creativecommons.org/licenses/by-sa/4.0/}{CC BY-SA 4.0}.
+  \end{itemize}
+\end{frame}
+\end{document}
-- 
cgit 1.4.1

