Let's assume we have this data:

[
    {
        "name": "Bertrand",
        "photo_count": 8846
    },
    {
        "name": "Boyd",
        "photo_count": 939
    },
    {
        "name": "Carlos",
        "photo_count": 204
    },
    {
        "name": "Cielo",
        "photo_count": 26
    },
    {
        "name": "Clementina",
        "photo_count": 3111
    },
    {
        "name": "Conor",
        "photo_count": 378
    },
    {
        "name": "Demarcus",
        "photo_count": 42923
    },
    {
        "name": "Eli",
        "photo_count": 290
    },
    {
        "name": "Enrico",
        "photo_count": 338
    },
    {
        "name": "Eula",
        "photo_count": 853
    },
    {
        "name": "Fernando",
        "photo_count": 84567
    },
    {
        "name": "Jovanny",
        "photo_count": 17909
    },
    {
        "name": "Maya",
        "photo_count": 3372
    },
    {
        "name": "Minnie",
        "photo_count": 13
    },
    {
        "name": "Morton",
        "photo_count": 16658
    },
    {
        "name": "Raymond",
        "photo_count": 22
    },
    {
        "name": "Saul",
        "photo_count": 3065
    },
    {
        "name": "Selena",
        "photo_count": 314
    },
    {
        "name": "Sigrid",
        "photo_count": 40
    },
    {
        "name": "Thora",
        "photo_count": 170
    }
]

number of items = 20

We want find out how many photos "Morton" has. This is sorted data (in order to determine the order of the names, we use a similar algorithm to that of the dictionary – start with the first letter and see which one comes first in the alphabet; if they are the same letter, move onto the next letter and repeat) and all the names are unique (so we cannot have a collision).

The mechanism for a binary search is not too complicated:

1. pick the middle item
2. check if the middle item is greater or smaller than the item we're looking for (if it is, then we stop searching and return the value)
3. pick either the lower half or the upper half of the list (lower half if the middle item is higher than the item we want, upper half if the middle item is lower than the one we want)
4. select the middle item of that list
5. repeat (unless we've reached the end)

Consider how we'd do that for the list above:

1. we start by selecting the middle item, i.e. "Eula" (don't forget – list indices start from zero in most programming languages). If we have an even number of items, we don't actually have a middle of the list – both the 10th and 11th (not zero-indexed) items of the list could be the middle. Here I've chosen to always use the one that comes first (so we round down from the median, which is the (n+1)/2th item).
2. We compare "Eula" to "Morton". As "Eula" begins with "E" and "Morgan" with "M" we conclude that "Eula" comes before "Morton". This means that we can ascertain that "Morton" is definitely in the top half of the list.
3. We now have this data

[
  {
    "name": "Fernando",
    "photo_count": 84567
  },
  {
    "name": "Jovanny",
    "photo_count": 17909
  },
  {
    "name": "Maya",
    "photo_count": 3372
  },
  {
    "name": "Minnie",
    "photo_count": 13
  },
  {
    "name": "Morton",
    "photo_count": 16658
  },
  {
    "name": "Raymond",
    "photo_count": 22
  },
  {
    "name": "Saul",
    "photo_count": 3065
  },
  {
    "name": "Selena",
    "photo_count": 314
  },
  {
    "name": "Sigrid",
    "photo_count": 40
  },
  {
    "name": "Thora",
    "photo_count": 170
  }
]

4. We pick the middle item in this list – i.e. "Morton" (there ten items, so I've picked the fifth one – but we could have picked the sixth)
5. We have a match!

One thing that is interesting to consider is how many items we have to look up with a binary vs a linear search.

• With a binary search we had to look at two items
• With a linear search we would have had to look at 15 items (assuming we started from the front – six if we started from the back)

Yes, I know that this list turned out to be quite convenient, which is why in general we look at the average performance of algorithms and their worst-case performance when we select them. We can consider the differences between these two algorithms mathematically.

For a binary search of a list containing 20 elements (assuming we always pick the value that comes first) once we pick element 9, we have conducted one lookup. Assuming the worse case (i.e. that we have to search the 10 element list, from 11-20 inclusive) we then select element five. In this case, we have done two lookups. Assuming that we then have to search the larger list again, we now search a five element list. We pick the middle item of that list – so we have now made three lookups. In the worst case, we now search a list of two items, so by the time we have searched the whole (sorted) list, we have looked at a maximum of five items.

In contrast, in the worst case linear search we have to look at an entire 20 items. Think of all the power savings you could get with a binary search!

You can also have a look at some further information on binary vs linear searching.

Broadly speaking, if you can use one (i.e. your data is sorted) you should prefer a binary search. If your data is not sorted, then you need to use a linear search.

Why prefere a binary search? It's much more efficient because it has to look at a lot fewer of the elements (consider this graph showing the average running times of a binary search vs a linear search as the number of elements increases).

There are three sorting algorithms that you need to be aware of, and although they might not exactly make your soul sing with joy, they do contain a lot of interesting computer science priniciples that you can and should apply to other 'problems' you find interesting.

function is_the_one_we_want(item):
    # this would be a user-defined function that takes an item
    # and returns `True` if and only if this is the one we want,
    # and `False` otherwise
    False

function find_item():
    # we look through each item
    for item in list:
        # check if this item is the one
        if is_the_one_we_want(item):
            # return from this function, aborting the loop
            return Item
    # once we've gone through the list, if we haven't found the item
    # then it cannot be in the list
    return None

That's it!

The main problem with a linear search is that it is not very fast (compared to other search algorithms that we can use). This is because we have to look over every single item in the dataset – sometimes this is not too bad (if the data happens to be near where we start), but in the worst case we have to look over every item in the dataset.

The other search algorithm in the GSCE is a binary search which is more efficient, but can only be used when the data is sorted (whereas a linear search does not require this.)

For example, if you are building a social media platform, you might have some data represented a bit like this:

[
    {
        user_id: 1, 
        name: "Alice", 
        file_locations: ["files/rocket.jpg", "files/solving_equations.mp4", ...]
    },
    {
        user_id: 2, 
        name: "Bob", 
        video_locations: ["files/dog.mp4", "files/bear.png", ...]
    },
    {
        user_id: 3, 
        name: "Charlie", 
        file_locations: ["files/one.png", "files/two.png", ...]
    },
    ...
]

(where ... means "and so on")

Which is all very well, until we want to get a list of Alice's videos because one of their friends has submitted a request to the server (assuming that we have checked that they have Alice's permission!!!). Here it is easy to see that Alice is the first person in our list, and therefore the problem is trivial. However, this is not always the case! Imagine you have a million users, and you want to find "Quentin" – in this case we have no idea where in the list Quentin is!

This is what a search algorithm is for – we might want to find the position of an item in a list (which is the, slightly boring, example that most textbooks give), or (much more frequently) we might want to find an item in our records based on a "key" (e.g. the name of the person).

There are a few search algorithms you should know about:

• linear search
• binary search

Imagine that you have a list a bit like this:

[12, 1, 8, 9, 7, 5]

To sort this using a bubble sort:

1. take the first two items (i.e. [12, 1]) and sort them – 12 > 1 so we swap them, such that our list now looks like:

[1, 12, 8, 9, 7, 5]

2. Take the next two items (i.e. [12, 8]) and sort them – 12 is also greater than 8, so we swap them (again) such that our list now looks like:

[1, 8, 12, 9, 7, 5]

3. We do the next thing for all the other elements – try doing it yourself. The end result should look like:

[1, 8, 9, 7, 5, 12]

4. We now return to step one (except that we use the list from step 3, in stead of the one we started with). We keep going until the list is sorted. One way of doing this is to keep a boolean variable denoting whether or not we swapped any values. If we didn't swap any values, then the list must be sorted, so we stop.

Steps:

1. pick up the next item in the list
2. look at all the previous elements in the list, and move it to the appropriate position
3. repeat until we've done all the items

e.g. for [12, 6, 21, 5, 9]

1. we start with 12. There are no previous elements, so we move onto the next item.
2. We look at 6. Comparing it to the only previous element 6 we can see that we want to move it before 12, so our list should look like [6, 12, 21, 5, 9].
3. We look at 21, and compare it to the previous elements. First we compare 21 and 12 – clearly 21 is greater than 12 (and we know that the previous elements must all be sorted, so we can stop there).
4. We look at 5. 5 is smaller than 21, so we compare it to the previous element. 5 is also smaller than 12 so we turn to look at 6. 5 is less than 6. Therefore our list is now [5, 6, 12, 21, 9]
5. We now look at 9. 9 is less than 21, so we look at 12. 9 is less than 12, so we look at 6. 9 is greater than 6, so we insert 9 after 6. Our list is now [5, 6, 9, 12, 21]

The final list is therefore [5, 6, 9, 12, 21].

further reading

• Have a look at this animation of an insertion sort

The core principle behind a merge sort is divide-and-conquer. This is a technique for solving programming problems which relies on discovering a way to divide the problem up into smaller problems, and then solving each of the smaller problems at the same time (see multicore machines for an explanation of why we can do multiple things at once on a computer).

We start with a list. Note that this list is a bit longer than the bubble sort example one because it demonstrates the advantage of merge sort better.

[1, 7, 7, 11, 18, 1, 23, 5, 10, 14, 3, 6, 20, 23, 28, 11, 28, 13, 8, 22]

The key to thinking about merge sort is that we are trying to maximise the number of operations that we can conduct in parallel (i.e. at the same time). We start by dividing up our list into groups of two (if we can't fit everything into neat groups of two – i.e. if the length of our list is not divisible by two –, we do what we always do in computer science and just try to make it fit as best we can – 'imperfect' solutions that work are fine).

1. Our list has twenty items (the format I have provided it in is designed to be easy to paste it as Python code, so you can follow along and experiment). First we divide our list into two halves. This means we have:

# let's call this list A
[1, 7, 7, 11, 18, 1, 23, 5, 10, 14]
# let's call this list B
[3, 6, 20, 23, 28, 11, 28, 13, 8, 22]

2. We now divide our halves again.

# let's call this list A_A because it is the first half of A
[1, 7, 7, 11, 18]
# let's call this list A_B because it is the second half of A
[1, 23, 5, 10, 14]
# let's call this list B_A
[3, 6, 20, 23, 28]
# let's call this list B_B
[11, 28, 13, 8, 22]

3. We do this again.

# let's call this list A_A_A because it is the first half of A_A
[1, 7]
# let's call this list A_A_B because it is the second half of A_A
[7, 11, 18]
# let's call this list A_B_A because it is the first half of A_B
[1, 23]
# let's call this list A_B_B because it is the second half of A_B
[5, 10, 14]
# let's call this list B_A_A because it is the first half of B_A
[3, 6]
# let's call this list B_A_B because it is the second half of B_A
[20, 23, 28]
# let's call this list B_B_A because it is the first half of B_B
[11, 28]
# let's call this list B_B_B because it is the second half of B_B
[13, 8, 22]

4. Once we've performed the division at stage 3, we have a lot of lists that are three elements long, and some that are two elements long. What we do here is divide up the three-element lists into a two element list and a one element long list. We leave the two element lists unchanged.

# let's call this list A_A_A because it is the first half of A_A
[1, 7]
# let's call this list A_A_B_A because it is the first half of A_A_B
[7, 11]
# let's call this list A_A_B_B because it is the second half of A_A_B
[18]
# let's call this list A_B_A because it is the first half of A_B
[1, 23]
# let's call this list A_B_B_A because it is the first half of A_B_B
[5, 10]
# let's call this list A_B_B_B because it is the second half of A_A_B
[14]
# let's call this list B_A_A because it is the first half of B_A
[3, 6]
# let's call this list B_A_B_A because it is the first half of B_A_B
[20, 23]
# let's call this list B_A_B_B because it is the second half of B_A_B
[28]
# let's call this list B_B_A because it is the first half of B_B
[11, 28]
# let's call this list B_B_B_A because it is the first half of B_B_B
[13, 8]
# let's call this list B_B_B_B because it is the second half of B_B_B
[22]

5. We have now finished our division. The next step is to merge and sort the lists. We want to merge all the X_X_X_A (where X_X_X is any three As or Bs in an order). Let's start with A_A_B_A and A_A_B_B (so [7, 11] and [18]). To sort these we do what is called "card-player's trick" where we pick the smallest item of each list (the pop function in most programming languages). First we pick the first item of [7, 11], which is 7. We then compare 7 to 18 – 7 is definitely smaller, so we place 7 as hte first item of our sorted list (so we now have [7]). We now pick the next smallest item (11) and compare it to 18. 11 is smaller, so we place it next in the sorted list – we now have [7, 11]. Because 18 is the only item remaining, we simply push it to the end, so we are left with [7, 11, 18] which is what we want. We do the same process for all the other four-lettered lists (e.g. A_B_B_A). If you don't understand this merging process, have a look at step 8 where I run through another merge.

# let's call this list A_A_A because it is the first half of A_A
[1, 7]
# let's call this list A_A_B (sorted)
[7, 11, 18]
# let's call this list A_B_A because it is the first half of A_B
[1, 23]
# let's call this list A_B_B (sorted)
[5, 10, 14]
# let's call this list B_A_A because it is the first half of B_A
[3, 6]
# let's call this list B_A_B (sorted)
[20, 23, 28]
# let's call this list B_B_A because it is the first half of B_B
[11, 28]
# let's call this list B_B_B (sorted)
[8, 13, 22]

6. We now sort all the elements at this level

# let's call this list A_A_A (sorted)
[1, 7]
# let's call this list A_A_B (sorted)
[7, 11, 18]
# let's call this list A_B_A (sorted)
[1, 23]
# let's call this list A_B_B (sorted)
[5, 10, 14]
# let's call this list B_A_A (sorted)
[3, 6]
# let's call this list B_A_B (sorted)
[20, 23, 28]
# let's call this list B_B_A (sorted)
[11, 28]
# let's call this list B_B_B (sorted)
[8, 13, 22]

7. We now merge them again.

# A_A (sorted)
[1, 7, 7, 11, 18]
# A_B (sorted)
[1, 5, 10, 14, 23]
# B_A (sorted)
[3, 6, 20, 23, 28]
# B_B (sorted)
[8, 11, 13, 22, 28]

8. We now merge again. Let's take A_A (sorted) and A_B (sorted). We have [1, 7, 7, 11, 18] and [1, 5, 10, 14, 23]. We know that these lists are sorted (in ascending order – i.e. from smallest to biggest). We want to form a new list of 10 items (combine the two lists of five). Let's think about the first item we want to place into this list. We know that the smallest item must be the first item of one of our two lists (because the first item of each list is the smallest item, and therefore the overall smallest item will be one of these). We remove the two items (one from each list), so we have 1 and 1. When we compare 1 and 1 we can see that they are equal, so we can push them in in either order into our list of ten sorted items – this list now looks like [1, 1]. We now pick the next two items. These are 7 (from A_A) and 5 (from A_B). Comparing these, it is clear that 7 is bigger than 5. Therefore we push 5 onto the sorted list (which now looks like [1, 1, 5]). We keep the 7, and compare it to the next item from A_B, which is 10. 7 is definitely smaller than 10, so we push it straight onto our sorted list, which now looks like [1, 1, 5, 7]. We remove the next smallest item from A_A (which is 7, again) and compare is to the item from A_B (the 10 we already removed). As before, 7 is smaller than 10, so we push it onto our list – which now looks like [1, 1, 5, 7, 7]. We remove the next item from A_A (i.e. 11) and compare it to the item from A_B (the same 10 we've already removed). 11 is bigger than 10, so we push the 10 onto the sorted list (which now looks like [1, 1, 5, 7, 7, 10, 11]). We now pick the next item from A_B (14) and conclude that 11 is less than 14, so we push 11 onto the list (so we have [1, 1, 5, 7, 7, 10, 11]). Now we pick the next item from A_A (18), which is definitely bigger than 14 (so we push 14 on the list, leaving us with [1, 1, 5, 7, 7, 10, 11, 14]). We remove the final item from A_B (23) and compare it to 18, noticing that 18 is less than 23, so we push 18 and then 23. The final list is therefore [1, 1, 5, 7, 7, 10, 11, 14, 18, 23].

[1, 1, 5, 7, 7, 10, 11, 14, 18, 23]
[3, 6, 8, 11, 13, 20, 22, 23, 28, 28]

9. We now finish our merging, and are left with the sorted list.

[1, 1, 3, 5, 6, 7, 7, 8, 10, 11, 11, 13, 14, 18, 20, 22, 23, 23, 28, 28]

why is merge sort fast(er)?

• We can do operations in parallel – for example, when we need to merge four lists at one stage, we can use multiple processor cores so that we can merge each pair of lists at the same time rather than having to merge the first pair and the second pair sequentially.

further reading

• This animation of a merge sort might help you to understand it.
• If you want a visual explanation of merge sort, then this one is quite good.
• not on any GCSE specifications as far as I can tell somewhat related to divide and conquer is "dynamic programming" which is a programming technique commonly used for solving games of strategy – see this presentation for information
• Table of sorting algorithms

Though this might not sing to your very soul in terms of how interesting it is, it does contain some interesting computer science principles that you can absolutely apply to other problems you find more interesting.

• bubble sort
• insertion sort
• merge sort

practice questions

practice questions

1. Given a table website_users write an SQL progarm to select all the data from this table.

further reading

1. The original paper introducing relational databases

The essence of defensive design is to anticipate how users might try to use a system in a malicious way.

further reading

• MalwareTechBlog

TODO

print("one") # print("one")

print("one")
# print("two")

# print("one")
print("one") # hello world
# some more random characters

load_times = [190, 170, 120, 80, 300, 210, 533, 1012, 50]

load_times = [190, 170, 120, 80, 300, 210, 533, 1012, 50]
sum_load_times = 0

# add the first item in `load_times` to `sum_load_times`
sum_load_times += load_times[0]
# add the second item in `load_times` to `sum_load_times`
sum_load_times += load_times[1]
# add the third item in `load_times` to `sum_load_times`
sum_load_times += load_times[2]
# and so on...

for i in range(len(load_times)):
    sum_load_times += load_times[i]

load_times = [190, 170, 120, 80, 300, 210, 533, 1012, 50]
# compute the sum
sum_load_times = 0
for i in range(len(load_times)):
    sum_load_times += load_times[i]
average = sum_load_times / len(load_times)
print("The average load time for this page is " + str(average) + "ms.")

for i in range(len(load_times)):
    sum_load_times += load_times[i]

for load_time in load_times:
    sum_load_times += load_time

def f(x):
    return x ** 2

def f(y):
    return y ** 2

def f(z):
    return z ** 2

def f(x):
    z = 32
    return z ** x
print(z)

def f(x):
    z = 32
    print(z)
    
f(x)

if <some condition>:
    <take some action>

def check_username(username):
    # condition 1
    if <some condition>:
        return False
    # condition 2
    if <some condition>:
        return False
    return True

# condition 1
if username[0] # some expression here:
    return False

def check_username(username):
    # condition 1
    if username[0].islower():
        return False
    # condition 2
    if <some condition>:
        return False
    return True 

function f(x)
    return x * x
endfunction

; ----------------------------------------------------------------------------------------
; Writes "Hello, World" to the console using only system calls. Runs on 64-bit Linux only.
; To assemble and run:
;
;     nasm -felf64 hello.asm && ld hello.o && ./a.out
; ----------------------------------------------------------------------------------------

          global    _start

          section   .text
_start:   mov       rax, 1                  ; system call for write
          mov       rdi, 1                  ; file handle 1 is stdout
          mov       rsi, message            ; address of string to output
          mov       rdx, 13                 ; number of bytes
          syscall                           ; invoke operating system to do the write
          mov       rax, 60                 ; system call for exit
          xor       rdi, rdi                ; exit code 0
          syscall                           ; invoke operating system to exit

          section   .data
message:  db        "Hello, World", 10      ; note the newline at the end

15
21

36

# reads a single line from the standard input and converts it to an integer
a = int(input())
# reads a single line from the standard input and converts it to an integer
b = int(input())
# outputs the result in the requested form
print(a + b)

x = 12

def square(number):
    x = number ** 2

square(12)
print(x)

# creates the global variable x
x = 12

# define the square function
def square(number):
    # 'capture' a reference to `x` inside this function
    # this reference will then be used when the function
    # is later called
    x = number ** 2

# invocate square, which updates the reference to `x` it has
square(12)
# prints the value of "x" to the console
print(x)

def square(number):
    return number ** 2
    
print(square(12))