diff options
Diffstat (limited to 'usth/ICT2.2/midterm/slides')
| -rw-r--r-- | usth/ICT2.2/midterm/slides/USTH.jpg | bin | 0 -> 375099 bytes | |||
| -rw-r--r-- | usth/ICT2.2/midterm/slides/bubbleplot.jpg | bin | 0 -> 20549 bytes | |||
| -rw-r--r-- | usth/ICT2.2/midterm/slides/slides.pdf | bin | 0 -> 980519 bytes | |||
| -rw-r--r-- | usth/ICT2.2/midterm/slides/slides.tex | 734 | ||||
| -rw-r--r-- | usth/ICT2.2/midterm/slides/squint.jpg | bin | 0 -> 70262 bytes |
5 files changed, 734 insertions, 0 deletions
diff --git a/usth/ICT2.2/midterm/slides/USTH.jpg b/usth/ICT2.2/midterm/slides/USTH.jpg new file mode 100644 index 0000000..d2190eb --- /dev/null +++ b/usth/ICT2.2/midterm/slides/USTH.jpg Binary files differdiff --git a/usth/ICT2.2/midterm/slides/bubbleplot.jpg b/usth/ICT2.2/midterm/slides/bubbleplot.jpg new file mode 100644 index 0000000..13ea13d --- /dev/null +++ b/usth/ICT2.2/midterm/slides/bubbleplot.jpg Binary files differdiff --git a/usth/ICT2.2/midterm/slides/slides.pdf b/usth/ICT2.2/midterm/slides/slides.pdf new file mode 100644 index 0000000..37fca3f --- /dev/null +++ b/usth/ICT2.2/midterm/slides/slides.pdf Binary files differdiff --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} diff --git a/usth/ICT2.2/midterm/slides/squint.jpg b/usth/ICT2.2/midterm/slides/squint.jpg new file mode 100644 index 0000000..1e86257 --- /dev/null +++ b/usth/ICT2.2/midterm/slides/squint.jpg Binary files differ |
