What are algorithms?

The Facebook news team was left pretty embarrassed over the weekend after firing their “trending content” news team and handing the job over to algorithms instead. Within a few hours, the new robot editors were promoting stories that ranged from the indecent (Ann Coulter being described with a four letter word) to the inaccurate (Megyn Kelly fired from Fox News) to the just plain wrong (the McChicken incident).

While things may not have worked out well with the algorithms in charge this time, it’s not an isolated case. Recent news stories have highlighted the dramatic effects that algorithms are having on our lives – shaping the news we see, the products we buy, the entertainment we experience, even the jobs we are offered. The problem is, for many people the word “algorithm” may as well be “abracadabra” – it’s like an incantation that describes the invisible magic taking place inside the sealed black box of your computer. Unless you hold a computer science degree, it’s hard to understand what’s actually happening when tech professionals talk about things like “deep learning” or “neural networks”.

And this is a bit of a problem. You don’t need to believe that the world of Skynet is just around the corner to realise that the looming issues entailed by self driving cars or medical robotics requires intelligent, informed oversight from everyday citizens.

So to do our bit to shed some light on this area, we’re running a series of posts on how common algorithms work and how they impact our daily lives. We’re kicking off this week with a gentle introduction to a simple algorithm for achieving an everyday task: finding a number in a contact list.

So what is an algorithm anyway? An algorithm is nothing more than a set of instructions given to a computer in order for it to carry out a required task. Many jobs that we give to computers can be broken down into simple steps that are repeated over and over again. Algorithm design is all about finding the best and fastest ways to break tasks down into steps that can be performed by computers.

For example, imagine looking for a person’s name in a phone book (old school, I know). You could start at the very first name and check each entry in turn. Now, if you are looking for Aaron Aalderson, you’re in luck! You’ll only need to check one name before finding the correct result.

But what if you are looking for Zoe Zwetschen’s number? You’ll need to check every single number before you find the correct entry.

Fortunately, if we know the phone book is in alphabetical order, we can find Zoe’s number much faster by using a strategy called “binary search”.

Let’s say we have a phone book with 100 entries, and this time we are looking for Hannah Halibut’s phone number. If we start at the beginning and check each entry in turn, if would probably take us about 30 checks to find her phone number.

screenshot (2)

Instead, let’s start by checking the middle entry on the list (#50). Let’s say that #50 is Larry Larrikin. We know that Hannah’s entry must be before Larry, because H comes before L in the alphabet. So straight away we can forget about checking entries #50 – #100. In one step we’ve eliminated half the possible entries.

screenshot (3)
screenshot (6)
screenshot (8)

 

So now our list of entries is only 50 items long. We check the new middle entry (number #25). #25 is the entry for Faye Foos . H comes after F in the alphabet, so we know that Hannah’s entry must be somewhere between #26 and #49, and we eliminate #1 – #25.

screenshot (9)

screenshot (12)
screenshot (14)

The next entry we check is halfway between the remaining numbers: #38. We keep going like this until we find Hannah.

screenshot (15)
screenshot (16)
screenshot (19)

Using our new, faster approach, we’re guaranteed to find Hannah’s entry after a maximum of 7 checks. That’s potentially over ten times faster than starting at the beginning of the list and checking every entry in turn.

And what if we needed to search through thousands or millions of names, instead of only 100? If we had a list of one million names, a computer using the binary search strategy would be 50,000 times faster than one that checked each name in turn. And if you managed to make a list containing all the people in the world sorted by name, you could find any person in less than 35 steps.

Looking up numbers in a phone book might seem like a simple example. But it’s this kind of thinking, that first breaks a task down into simple repeatable steps and then considers how many time those steps need to be repeated, that is at the heart of all algorithmic analysis.

And hey, next time you’re scrolling through your contact list, you might even find yourself performing a binary search – pretty cool huh? And if you’re interested in reading more, binary search can even help you win at Guess Who.

If you have questions about how particular algorithms work please leave a comment below and we’ll try to cover it in an upcoming post. So far we’re planning to look at how Netflix suggests movies you might like, how Facebook can recognise your face from a photo, and just what is a neural network anyway?

P.S. A quick shout out to the following sites that came in handy for generating the animations for this post: