From 44f2051baded0c87b86da84ab8f4b62618a1f35a Mon Sep 17 00:00:00 2001
From: Mohit Agarwal <mohit.agarwal@sky.com>
Date: Thu, 14 Oct 2021 17:37:05 +0100
Subject: Finished notes. Needs proofreading.

---
 notes/algorithms.tex | 79 +++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 57 insertions(+), 22 deletions(-)

(limited to 'notes/algorithms.tex')

diff --git a/notes/algorithms.tex b/notes/algorithms.tex
index c745b72..4801766 100644
--- a/notes/algorithms.tex
+++ b/notes/algorithms.tex
@@ -22,15 +22,12 @@ an algorithm is. This might be in how quickly an algorithm can be
 computationally run, or how much memory is used in running the
 algorithm.
 
---best and worst case
-
 \section{Searches}
 
-Let us say that we have a list of numbers $n$ where $n =
-\{2,6,4,7,8,3,9,0\}$ Let us now consider algorithms to `search' for a
-value in the list $n$.
-
---key
+Let us say that we have a list of numbers $n$ where \[n =
+\{2,6,4,7,8,3,9,0\}\] Let us now consider algorithms to `search' for a
+value in the list $n$. We can call this value the `key' in our search
+$k$.
 
 \subsection{Linear search}
 
@@ -56,35 +53,73 @@ would immediately find it.
 \subsection{Binary search}
 
 Consider searching for an item if the list is already sorted, so $n$
-would become $\{0,2,3,4,6,7,8,9\}$. Now if we wanted to search for an
-item we could think of it in a way different from linear search.
-Let us say we are looking for the value $6$. One way to do this is to
-start in the middle, at the value $4$, and comparing it to $6$. $4 <
-6$, so because are list is already sorted, we can discard all the
+would become \[\{0,2,3,4,6,7,8,9\}\] We can now search in a different
+way. Let us say the value we are looking for ($k$) is  $6$. We could
+start in the middle, at the value $4$, and comparing it to $6$.  \[4 <
+6\] so because are list is already sorted, we can discard all the
 numbers left of and including $4$, knowing that we are not discarding
-$6$, so our list becomes $\{6,7,8,9\}$. Let us do the same again,
-picking the middle value $7$ and comparing it to $6$. $7 > 6$, so we
+$6$, so our list becomes \[\{6,7,8,9\}\] Let us do the same again,
+picking the middle value $7$ and comparing it to $6$. \[7 > 6\] so we
 can discard everything right of and including $7$, knowing that $6$
 will not be discarded, as the list is sorted. Thus our list becomes
-$\{6\}$. Let us pick the middle value $6$ and compare it to $6$. $6 =
-6$, thus we have found the element. If there were no more elements
+\[\{6\}\] Let us pick the middle value $6$ and compare it to $6$. \[6
+= 6\] thus we have found the element. If there were no more elements
 left and we had not found our key, then we would know it is not in the
-list.
-
---unclear
+list. This is \textit{binary search}.
 
 The major drawback to binary search is that the list must be sorted
 for the sort to work. However, once the list is sorted, it is
-significantly faster (less time complex) then linear search, as each
-time the search is performed, half of the list is `discarded', so far
-fewer comparisons will be made.
+significantly faster (less time complex) then linear search, as for each
+comparison, half of the list is `discarded', so far fewer comparisons
+will be made.
 
 \section{Sorts}
 
+For binary search and for many other reasons we may have a list of
+values that we want to sort. Let us once again say that we have a list
+of numbers $n$ where \[n = \{2,6,4,7,8,3,9,0\}\] 
+
 \subsection{Bubble sort}
 
+Bubble sort involves running through the list and comparing each
+element to the element after it. If they are out of order, they are
+swapped and we keep going through the list. If we pass through the
+entire list without making any swaps, then the list is sorted. For
+example, in $n$, we would start with $2$ and compare it to $6$. These
+are in order, so we move to $6$ and compare it to $4$. These are out
+of order so we would swap them. Here are some but not all steps on the
+original list $n$
+
+\begin{align*}
+    &n = \{2,6,4,7,8,3,9,0\} \mbox{ comparing 2 and 6} \\
+    &n = \{2,4,6,7,8,3,9,0\} \mbox{ comparing 6 and 4, \textit{swap}} \\
+    &n = \{2,4,6,7,8,3,9,0\} \mbox{ comparing 6 and 7} \\
+    &n = \{2,4,6,7,8,3,9,0\} \mbox{ comparing 7 and 8} \\
+    &n = \{2,4,6,7,3,8,9,0\} \mbox{ comparing 8 and 3, \textit{swap}} \\
+    &...
+\end{align*}
+
 \subsection{Merge sort}
 
+Merge sort begins by splitting a list into sublists, each containing
+only one element. These lists are then merged until they again form
+one big list. The merging process begins by running through two lists
+at the same time and adding the smaller value to the output. For
+example, let us say we want to merge the lists \[\{1,3,5\}\] and
+\[\{2,4,6\}\] Then we would start at the beginning of each list and
+sequentially add the smaller value between the lists to the output
+
+\begin{align*}
+    list\ 1  &&list\ 2  &&output\ list\\
+    \{1,3,5\}&&\{2,4,6\}&&\{\}       &&\mbox{}\\
+    \{3,5\}  &&\{2,4,6\}&&\{1\}      &&\mbox{Comparing 1 and 2, we start with 1}\\
+    \{3,5\}  &&\{4,6\}  &&\{1,2\}    &&\mbox{Comparing 3 and 2, we add 2}\\
+    \{5\}    &&\{4,6\}  &&\{1,2,3\}  &&\mbox{Comparing 3 and 4, we add 3}\\
+    \{5\}    &&\{6\}    &&\{1,2,3,4\}&&\mbox{Comparing 5 and 4, we add 4}\\
+    \{\}     &&\{6\}    &&\{1,2,3,4,5\}&&\mbox{Comparing 5 and 6, we add 5}\\
+    \{\}     &&\{\}     &&\{1,2,3,4,5,6\}&&\mbox{Comparing nothing and 6, we add 6}\\
+\end{align*}
+
 \section{Programming languages}
 
 Programming languages are useful to humans in writing algorithms for
-- 
cgit v1.2.3

