1 files changed, 86 insertions, 0 deletions
diff --git a/notes/algorithms.tex b/notes/algorithms.tex
new file mode 100644
index 0000000..581a5e5
--- /dev/null
+++ b/notes/algorithms.tex
@@ -0,0 +1,86 @@
+\chapter{Algorithms}
+
+An algorithm is a set of instructions that is followed, generally to
+complete a task or solve a specific problem. Although algorithms are
+often thought of in terms of computers, both humans and computers can
+follow algorithms, an example of which might be Euclid's algorithm
+\footnote{\url{https://en.wikipedia.org/wiki/Euclidean_algorithm}} for
+calculating the highest common factor of two numbers.
+
+\section{Representing algorithms}
+
+Pseudocode is recommended and the AQA teaching guide gives the style
+guide for pseudocode, however religious following of this is not
+important, as long as code is clear and consistent. 
+
+\section{Complexity}
+
+We might want to compare different algorithms, particularly when they
+accomplish the same task, such as sorting an array of numbers. In
+particular, we might want to see how resource intensive or `complex'
+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
+
+\subsection{Linear search}
+
+The most obvious way to do this is arguably `linear search'. This
+involves looking at each element and comparing it to what we want to
+find. In our list $n$, let us say we want to find the element $8$. We
+would start on the left and go through $2,6,4,9$ having compared them
+each to $8$ and having not yet found it. Yet when we compare the next
+element ($8$) to $8$, it will be a match, and we can say we have found
+the element. 
+
+On the other hand, if we are looking for the value $1$, we would go
+through each element in the list, and not find it, and could thereby
+declare that it is not in the list. This suggests that in the worst
+case the time complexity become quite large, as the size of the list
+gets larger because if the element is the last element in the list or
+is not in the list at all the algorithm will have to compare against
+every single other element in the list. The best case for this
+algorithm would be if the first element in the element we are looking
+for: if we were looking for $2$ in $n$, it is the first element and we
+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
+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
+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
+left and we had not found our key, then we would know it is not in the
+list.
+
+--unclear
+
+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.
+
+\section{Sorts}
+
+\subsection{Bubble sort}
+
+\subsection{Merge sort}