1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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}
|
