Describing a solution

We live in algorithmic times. Solutions to past problems have been described as algorithms for us to use today. It is important when describing a solution to ensure that it is clear and unambiguous for OTHERS to understand.

Algorithms are written down in one of three ways:

• Structured English

• Pseudocode - great for detail

• Flowcharts - quickly read and understood but not good for details

An algorithm that EVERYONE MUST KNOW is how to create a strong password for every website we visit (written in Structured English):

1. Take the last character of URL of website you want to sign up to (eg. Facebook) = k

2. Append the first character of each member of the band you like (eg. Beatles: John, Paul, George and Ringo) = kjpgr

3. Append the first character of the URL of the website you want to sign up to = kjpgrf

4. Append some special characters "!%$" at the end = kjpgrf!%$

Common algorithms that are important for Computer Scientists:

Searching

• Linear search

• Binary search

Sorting

• Bubble sort

• Merge sort

• Insertion sort (GeekForGeek, Khan Academy)

CLICK HERE - Compare all sorting algorithms together

CLICK HERE - Watch algorithms in action visually (VisualAlgo)

This algorithm does not assume a sorted list.

Searches each list item in turn until the required item is found.

• Worst case performance: O(n)

• Best case performance: O(1)

• Average performance: O(n)

This algorithm assumes a sorted list.

Divides the search space into x2 equal sets then compares the required item with each set. It discards the set that cannot contain the required item and repeats the process with the resultant set.

• Worst complexity: O(log n)

• Best complexity: O(1)

• Average complexity: O(log n)

Starts at one end of the list, compares the current item with its neighbour. If it is larger then they swap. The current item moves onto the next list item and the process repeats until the last item. Then the process is repeated from the end of the list again.

Deterministic version: This algorithm will blindly repeat n^2 times.

Non-deterministic version: This algorithm will stop iterating when there have been no swaps.

• Worst complexity: O(n^2)

• Best complexity: O(n)

• Average complexity: O(n^2)

Split the list into x2 lists: sorted and unsorted. The sorted list contains just one number, the unsorted list contains all others. Take each number in the unsorted list in turn, then track back through each number in the sorted list until the number can be inserted in its sorted position. Repeat this process until the unsorted list is empty.

• Worst complexity: O(n^2)

• Best complexity: O(n)

• Average complexity: O(n^2)

Continually divide the list until you get to individual items. Then 'merge' neighbouring items back together, sorting them as you merge. Once items are merged, repeat the process between neighbouring pairs. Then neighbouring sets and so forth until the list is reconstructed sorted.

• Worst complexity: O(n*log(n))

• Best complexity: O(n*log(n))

• Average complexity: O(n*log(n))

Why so many algorithms that do the same thing?

You may wonder why there are x3 different ways to sort numbers. There are in fact lots more than x3 but why?

We live in Algorithmic times. People sit down and solve problems, eg. how to sort some numbers. Then they write the solution down as an algorithm. Then release it to the world - to live forever. Then another person sits down to solve the same problem, eg. sorting numbers, and writes their algorithm and releases it to the world. We now have x2 algorithms that sort numbers. They do the same job but in a different way.

Evaluating an algorithm

There is more than one way to sort a list of numbers of search a list of numbers, so which do you use? Pick at random? Eeny meeny miney moe?

Different algorithms do the job (sort or search for things) in different times, under different conditions. An algorithm is evaluated in terms of:

• its speed (called time complexity) and

• how much memory it takes (space complexity)

in doing its job. The test results are written down as "Big O notation".

You choose the algorithm based on the conditions it will operate under and how much time and space you have to use.

CLICK HERE - GCSE Algorithm questions

Gap task: One hundred doors

CLICK HERE - STEM Impact toolkit