Algorithms The Secret To Our Digital World

Algorithms the secret to our digital world

Algorithms are simple step-by-step recipes. Inventing them requires incredible creativity and genius but using them is just a matter of following instructions and this is why algorithms are perfect for computers. As we search for love, travel the world, save lives or even order items on-line, there are step-by-step instructions working quietly behind the scenes. More and more, they are ruling our lives. These bite-sized chunks of mathematics have become central to our daily lives. However because they are invisible, we tend to take them for granted, even misunderstand them. They are the secret to our digital world, and so much more!

Ancient Algorithms

Today we are going to talk about some of my favourite algorithms and reveal where they came from. Algorithms are ancient, and are by no means a modern day invention, however, the huge growth in information technology has harnessed the power of the algorithm and now we can't live without them. Even when we're baking a cake, we're following an algorithm. I love algorithms, not only are they impressive problem solvers, but also strangely beautiful, tapping into the mathematical order that underpins the universe.

Laying Perfect Tiles

The oldest algorithm we know of was devised to solve a mathematical problem. It was first written down by the Ancient Greek mathematician Euclid. Euclid's Algorithm, as it's known, is a method for finding the greatest common devisor. The greatest common devisor is the largest number that will divide into a pair of other numbers without leaving a remainder. So, in this case, four divides into both eight and 12 without a remainder. It is simple to find for small numbers, but much more tricky for large ones. While Euclid was the greatest mathematician of his day, his algorithm could have made him a fortune as a tiler. Let me show you why... Imagine you have ve got a rectangular-shaped floor and you want to find the most efficient way to tile it with square tiles. In other words, what is the largest square tile that will exactly divide the dimensions of the floor with nothing left over? This is, in fact, a geometric version of the greatest common devisor problem. The dimensions of the floor are the two numbers and the size of the tiles, which we're going to try and work out, is their greatest common devisor. We're going to follow Euclid's Algorithm step by step to show how it is able to find the perfect sized square tile for this floor. According to Euclid's Algorithm, we need to start filling the rectangle with square tiles corresponding to the smallest of the two dimensions. This is the first stage of the job. Euclid's Algorithm then tells us to do exactly the same thing again with this rectangle. At each stage, the algorithm tells us to select square tiles So this time, our square tiles perfectly fill the leftover space. Now, my square tile has dimensions 15x15. So Euclid's Algorithm tells us that the greatest common devisor of 150 and 345 is 15. I'm not suggesting you use Euclid's Algorithm every time you need to order some tiles, but the amazing thing is that this simple step-by-step method finds the perfect square tile whatever the dimensions of the floor. Euclid's Algorithm may appear to be just a mathematical technique, but it very elegantly fulfils all the criteria for an algorithm. It is a precisely stated set of instructions, the procedure always finishes, and it can be proven that it works in all cases.

The Chilli Game

Here is an example of a game with a jar full of chocolates and one red hot chilli. The aim of the game, is not to be left with the chilli at the end. What my opponent does not know is that I'm playing it with the help of an algorithm! OK. Ready? I'm going to go first, so remember, you can take one, two or three chocolates at a time. I'm not a greedy guy, so I'll just take one. Now, your turn. Each player takes on their turn, between one and three chocolates. Whatever my opponent does, my algorithm will tell me how to respond OK, I'll take two and it is your turn again. My opponent then takes three and then I will take one and that means we have just one chilli left... So Yeah, so you have to eat the chilli!!

Let me reveal how the algorithm I was using helped me win as it is the only way to learn. So, the key here is to think about grouping things in fours. 13 chocolates divides into three groups of four, with one left over. So, by taking one chocolate in the first round and then four minus whatever the other player takes in the subsequent rounds, this algorithm ensures that the other player is always left with the chilli. It really is as simple as that, it works every time. The essence of a really good algorithm, its magic, if you like, is mathematics. The best algorithms are those that tap into the underlying mathematical structure hiding beneath a problem.

Algorithms In Our Everyday Lives

You might have noticed that when you take a photo with your phone, it draws a box around any face, like the picture below. This is the result of a special face-detection algorithm which helps to keep the face in the photo in focus. Like all algorithms, this one solves a problem. In this case, it is finding a human face. However when we make a fake face, in this case we tried a face made of fruit, it does not detect a human face in a photo. At their root, algorithms are little more than a series of step-by-step instructions. This one works by methodically scanning the image looking for four particular abstract patterns that are associated with a face. When these are detected one after another, the algorithm indicates it's found a human face. The process taps into the underlying pattern behind all faces, no matter what shape or size. The end result is just one example of how algorithms have made our lives easier.

The Old Original Google Algorithm

The power of algorithms is that you don't have to reinvent the wheel each time. They're general solutions to problems. This holds as true for ancient algorithms as for modern ones. In 1998, in this garage in Menlo Park in California, an important piece of algorithmic history was made. Inside were two PHD students from Stamford University. Larry Page and Sergey Brin. Their aim was to come up with a search engine that could find things efficiently on the World Wide Web. Out of these humble beginnings, Google was born but Google wouldn't be Google if it wasn't for the algorithm that Larry and Sergey created, called PageRank.

PageRank was the algorithm at the heart of the first incarnation of the Google search engine. Now, technically, it's not a search algorithm, but a ranking algorithm. So when you type a query into a search engine, what PageRank does is to rank all of those pages so the one at the top is the one you are more likely to be interested in. Larry and Sergey came up with the idea for the pagerank algorithm and to use it as a ranking system to improve the quality of web search. I remember myself at the time, you used a web search engine like AltaVista. You would have to click the Next Page link a lot of times to find what you were looking for. PageRank was one of the reasons why Google was so much better than the existing search engines at the time. The inner workings of PageRank are hidden from view on the World Wide Web.

So to reveal how it does its job, we're going to use the PageRank algorithm to rank the players of a football team. PageRank looks at two things. It looks at the incoming links to a web page, that is the other pages that link to the page, and it looks at how important those pages are. In our demonstration to show algorithm, the players in the football team are the web pages and the passes between them are the web links. The input for the algorithm. Generally speaking, the PageRank algorithm will give a higher rank to a website if it's got a lot of links coming from other websites. So in the case of football, if a player gets more passes from the rest of the team, then they'll be ranked higher. However as always, it is not quite that simple because the PageRank algorithm actually gives more weight to a link from a website that itself has a high page rank. So actually, a pass from a popular player is worth more than a pass from a player who's hardly involved in the game at all. Note that the importance of a page depends on the importance of the pages that link to it. This means that you have to compute page rank for all the pages at the same time and you actually have to repeat the computation because, each time, you'll update the importance of all the pages. That in turn will then influence the importance of the pages that those pages link to. At the end of the match, the job of the algorithm is done. I think the PageRank algorithm is probably my favourite algorithm of all time and it's amazing that it can be applied not just to the World Wide Web, but analysing a football match.

Page-rank is the beautiful bit of mathematics at its heart that always seems to find the website I'm looking for (although not these days, sadly page rank is only one of the 150 ish factors that Google uses to rank a web site). I think PageRank is seen as a very important part of Google's early development. PageRank was the secret to why the search engine, that Larry and Sergey built in the 1990s, was so successful. Now, Google handles over 3.5 billion searches every day. It's the world's most poplar search engine worth more than $450 billion. Not bad for two PhD students working out of a garage.

The Bubble Sort Algorithm

Computers are still just machines they just do repetitive tasks at phenomenal speeds. So they are absolutely perfect for performing these repetitive tasks that are unambiguously defined and can be done in a finite amount of time. Computer code is basically making an algorithm specific. Lots of types of algorithms have been created with a computer in mind and some of the most important are sorting algorithms. In 1963 two computer scientists first formally wrote down one of the most iconic sorting algorithms of all-time. It's called Bubble Sort. So I am going to try to describe how this works, so imagine sorting a set of many blocks of different sizes. Remember Bubble Sort gets its name because with each round of the algorithm, the largest unsorted object bubbles to the top, so this should give you a clue to how it works. Now, the bubble sort algorithm says to consider the objects in pairs and swap them over if they're in the wrong order. So we're going to start at one end here and work our way to the top. So I consider the first two, they're in the wrong order, so I swap them over. Consider the next pair, they're in the right order, so I leave them as they are. Consider the next pair, they're in the wrong order, so I swap them and we just continue doing this. Now the bubble sort algorithm says to go back to the beginning and repeat the process over and over again until the objects are in order. The algorithm stops when there are no pairs to swap round. So the bubble sort algorithm has successfully done its job.

Here is an example of the bubble sort algorithm (function) written in classic asp / vbscript that we actually use on some of our sites.

Sub BubbleSort(ByRef a)
On Error Resume Next
iMax = UBound(a)

For i = 0 To iMax - 1
Start = a(i)
iNew = a(i)
swap = i

For j = i + 1 To iMax
If a(j) < iNew Then

swap = j
iNew = a(j)
End If
Next

If swap <> i Then
a(swap) = Start
a(i) = iNew
End If
Next y
End Sub

The Merge Sort Algorithm

Well that is all well and good, but bubble sort is not always the right algorithm for the job. At the System Development Corporation in California (considered to be the world's first computer software company) a man called John von Neumann was the scientific genius who helped pioneer the modern computer, game theory, the atomic bomb and, as it turns out, invented a sorting algorithm. He devised it to work on this, one of the world's earliest electronic computers, which he'd helped design. The algorithm is called merge sort. The merge sort algorithm works on a principle of divide and conquer and consists of two parts. The first bit is the dividing part. This involves splitting everything into smaller groups. Next is the conquering bit. The groups are now merged back together but as the two groups merge, the sizes of the objects are compared one pair at a time so that the merged group becomes sorted. It's much, much faster than bubble sort. In fact if you race the two algorithms side by side with the same data, and if its that data is big data, then Merge Sort gradually gets faster and faster as it divides the load down... and Bubble Sort well, just does not work very well.

Article Updated May 27th 2022