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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
\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.
\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$. We can call this value the `key' in our search
$k$.
\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\}\] 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
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. 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 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
computers to run. There are \textit{high level languages} (such as
Python, Haskell, and C) which are easier for humans to write and
understand, \textit{low level languages} (assembly code) which are
human readable but directly represent machine code, and machine code
which is not readable by humans as it is binary code but is the only
information the computer actually understands and runs.
Some languages (such as C) are \textit{compiled}. This involves the
entire \textit{source code} being turned into a machine code file by
the compiler. Other languages (such as Python) are
\textit{interpreted}. Here, an interpreter turns a line of code into
machine code, runs it and then moves onto the next line. The benefit
of a compiler is that once compiled, the machine code file is very
fast to run. However, an interpreter offers easier development as
there are no long compile times but it is slower than code that is
already compiled.
|
