Original subtitles

Encoded by

Without us noticing, modern life has been taken over.

As we search for love, shop online,

travel the world,

even as we save lives,

there are step-by-step instructions working quietly behind the scenes.

More and more, they are ruling our lives.

They're called algorithms.

Algorithms are everywhere.

These bite-sized chunks of maths have become central

to our daily lives.

But because they are invisible, we tend to take them for granted,

even misunderstand them.

LAUGHTER

They are the secret to our digital world, and so much more.

'In this programme, I'm going to show you some of my favourite

'algorithms to reveal where they came from...'

Algorithms are ancient.

'..how they work...'

The challenge is to find the shortest route...

These are the rough instructions that you would use.

..for returning to your starting point.

'..what they might be able to do in the future.'

- The algorithm's kind of writing itself? Or...? - Absolutely.

'..and how we can't live without them.'

Even when we're baking a cake, we're following an algorithm.

As a mathematician, I love algorithms.

Not only are they impressive problem solvers,

but also strangely beautiful, tapping into the mathematical

order that underpins how the universe works.

Welcome to the weird and wonderful world of algorithms.

Most of us carry one of these around.

Now, you might have noticed that when you take a photo

with your phone, then it draws a box around any face, like this.

This is the result of a special face-detection algorithm

and it helps to keep the face in the photo in focus.

'Like all algorithms, this one solves a problem.

'In this case, finding a human face.

'While it's not fooled by a face made of fruit,

'it does detect a human face in a photo.

'So, how does it do it?

'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

'associated with a face.

'When these are detected one after another,

'then 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.

- I'll do it! - I'll do it! - I was here first! - OK.

So, off you go.

'We tend to associate algorithms with computers, smartphones

'and the internet.

'But they are not exclusive to the world of technology.

'My day job is Professor of Mathematics at Oxford University.

'And one of the things I enjoy most is keeping

'the students on their toes.'

OK, I'll take one.

Here, we're playing a mathematical game with a jar

full of chocolates and one red hot chilli.

'The aim is not to be left with the chilli at the end.

'But what these students don't know,

'is that I'm playing it with the help of an algorithm.'

- OK. Ready? BOTH: - Yeah.

Right, 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.'

You've taken two, OK. So, I'm going to take... I'll take two.

'Whatever my opponent does, my algorithm that tells me

'how to respond.'

OK, I'll take two.

And your turn again. SHE LAUGHS

Oh, yeah.

- So I'll take...three. - Three. And I'll take one.

- And just a chilli left... - So, wait. Is that me? - Yeah, so you have

- to eat the chilli. - Oh, no! - So, there you go.

'Let me reveal how the algorithm I was using helped me win.'

It's the only way to learn.

So, the key 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.

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.

OK, pop the chilli back.

I'll be introducing you to some of the algorithms that have

become the beating heart of modern life.

But first, I want to show you that, for all their modern

applications, algorithms are extremely old.

In fact, they predate computers by thousands of years.

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's 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'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's 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

corresponding to the shortest side of the rectangle.

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's a precisely stated set of instructions, the procedure

always finishes, and it can be proven that it works in all cases.

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,

then there are literally millions of pages which will match that query.

What PageRank does is to rank all of those pages so the one

at the top is the one you're more likely to be interested in.

Larry and Sergey came up with the idea to do PageRank

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 the cleverness of the PageRank

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.

It's 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.

This is a visualisation of the algorithm at work.

The stats are the players' current ranking. The output of the algorithm.

And every time there's a pass, these rankings are updated.

When Google uses this algorithm, it only changes once thing - the input.

In place of passes, it uses web links.

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.

And that in turn will influence

the importance of the pages that those pages link to.

At the end of the match, the job of the algorithm is done.

If we wanted to search for the key player in the team,

this is PageRank's answer.

Player 11 has the highest PageRank score.

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, as well.

But for me, it's the fact that there's a beautiful bit of

mathematics at its heart that always seems to find

the website I'm looking for.

Within Google, 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.

And the company is worth more than 450 billion.

Not bad for two PhD students working out of a garage.

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.

Computers are just machines.

They just do repetitive tasks at phenomenal speeds.

Unbelievable speeds.

So they're 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.

So the algorithm is the kind of idea.

How would you solve the problem?

These are the rough instructions that you would use.

And then that can be translated into particular code.

Lots of types of algorithms have been created with a computer in mind.

And some of the most important are sorting algorithms.

Now, the job of a sorting algorithm is to put things in order.

And they have lots of uses.

For example, on the internet, information gets

broken down into packets of data which then get sent across the web.

Now, to reassemble that data,

sorting algorithms are absolutely crucial to putting this data

back in the correct order so that we can view the picture,

or read the email we've just been sent.

This is the System Development Corporation in California.

It's considered to be the world's first computer software company.

And it was here in 1963 that two computer scientists first formally

wrote down one of the most iconic sorting algorithms of all-time.

It's called bubble sort.

And here's an example of bubble sort in action,

sorting blocks instead of numbers.

It gets its name because with each round of the algorithm,

the largest unsorted object bubbles to the top.

Like all our algorithms so far, there's method in the madness.

To see how this algorithm works,

we're going to use it to sort eight objects.

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 this end here and work our way to the top.

So I consider these 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 this 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.

I've now got the objects perfectly ordered,

according to ascending height.

Bubble sort is elegantly simple and straightforward.

But if the scale of the sorting task is huge, say, organising vast swathes

of data, then there might be better sorting algorithms for the job.

This is John von Neumann,

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 it consists of two parts. The first bit is the dividing part.

This involves splitting everything into smaller groups.

And now comes the conquering bit.

The groups are now merged back together.

But as I merge the two groups, I compare the sizes of the objects

one pair at a time so that the merged group becomes sorted.

Now, the merge sort algorithm might look rather similar to the

bubble sort, but where it comes into its own is that with a larger

number of objects, it's much, much faster.

So let's see how merge sort compares in speed to bubble sort.

It's time for a battle of the algorithms!

Here we've got bubble sort on the bottom and merge sort on the top.

And we've got them sorting 1,000 objects.

Now, although they'll both produce the same end result,

you can already see merge sort is getting there much faster.

And this difference in performance gets more pronounced

the more objects they're asked to sort.

LAUGHTER

Well, er...

- I'm sorry, maybe... - No, no, no, no, no.

I-I think...I think, er...

I think the bubble sort would be the wrong way to go.

LAUGHTER

APPLAUSE

Come on. Who told him this?

Merge sort beats bubble sort hands down

for sorting large amounts of data.

But in the crazy world of algorithms, there are many,

many different ways to sort.

At the last count,

there were over 20 different types of sorting algorithms.

All weirdly achieving the same result, but by different means.

- So there's bubble sort, there's merge sort. - Insertion sort.

- There's heap sort, there's quick sort. - Timsort.

You've got gnome sort.

There's pigeonhole sort, which is also called radix sort.

There's bogosort, which might never finish.

There's no such thing as the best sorting algorithm.

Each has its own pros and cons.

And which one gets used

often depends on the specifics of the problem.

I think the beauty of studying algorithms is to try to aspire

for solutions that are as elegant and efficient as possible.

I actually think bubble sort's very pretty. I like it.

Merge sort's beautiful.

We really couldn't live without them.

Sorting algorithms bring order to the world.

So far, we've seen algorithms tackle the tiny

problems of sizing our bathroom tiles and sorting our data.

But how well do they cope with the messy world of love?

Online dating is really popular these days.

In fact, one survey suggests that over a third

of recent marriages started online.

How these dating websites work is that they use something called

a matching algorithm.

They search through the profiles, try to match people up according

to their likes and dislikes, personality traits and so on.

In fact, the algorithms seem to be better than humans.

Because recent research has shown those who meet online

tend to be happier and have longer marriages.

I'll ask you to receive your prizes from His Majesty the King.

In fact, matching algorithms have quite a lot to brag about.

Because in 2012, for the first time, a Nobel Prize was awarded

because of an algorithm.

A matching algorithm created by the late David Gale

and mathematician Lloyd Shapley,

seen here receiving his share of the prize.

The story begins in the 1960s when Gale and Shapley wanted to

solve a problem concerned with college admissions.

How to match up students to colleges so that everyone got a place.

But, more importantly, was happy, even if

they didn't get their first choice.

They called it the stable marriage problem.

The stable marriage problem goes like this.

Suppose you've got four women and four men

and they want to get married.

Now, they've ranked each other according to their preferences.

So, for example, the Queen of Hearts here,

first choice is the King of Clubs.

Second choice, King of Diamonds,

and her last choice is the King of Hearts.

So the challenge here is to play Cupid and pair up the kings

and queens so that each one gets a partner, but, more importantly,

so that the marriages are stable.

A stable marriage means that the kings and queens don't

necessarily get their first choice, but they get the best on offer.

For example, if I paired the King of Hearts and the Queen of Hearts

and the King of Spades and the Queen of Spades,

this would be an unstable marriage.

Because the King of Spades doesn't really like the Queen of Spades.

He'd prefer the Queen of Hearts.

The Queen of Hearts, in her turn,

doesn't really like the King of Hearts.

She'd prefer the King of Spades.

So these two are going to run off together in this pairing.

Where there's a problem, there's an algorithm not far behind.

In 1962, Gale and Shapley came up with

their Nobel-Prize-winning algorithm.

A step-by-step recipe which always finds perfectly-stable marriages.

So in the first round of the algorithm,

the queens all proposed to their first-choice kings.

So the Queen of Spades' first choice is the King of Spades.

She proposes to the King of Spades.

The Queen of Hearts' first choice is the King of Clubs,

so she proposes to the King of Clubs.

The Queen of Diamonds' first choice is the King of Spades.

And the Queen of Clubs' first choice is also the King of Spades.

So King of Spades seems to be the Darcy of this royal court.

Now, the King of Spades has got three proposals.

So he chooses his most popular queen,

who is actually the Queen of Diamonds, and rejects the other two.

So we have two provisional engagements, two rejections.

We now remove the rejected queen's first choices.

And it's time for round two.

So the Queen of Spades is going to propose to the King of Diamonds.

And the Queen of Clubs proposes to the King of Clubs.

But now the King of Clubs has got two proposals

and actually prefers the Queen of Clubs.

So he rejects the Queen of Hearts, his provisional

engagement on the first round of the algorithm,

and we have to start again.

In each round, the rejected queens

propose to the next king on their list.

And the kings always go for the best offer they get.

In this round of the algorithm, she proposes to the King of Hearts

and finally, everyone's paired up with a single queen and king

and all the marriages are stable.

The Gale-Shapley algorithm is now used all over the world.

In Denmark, to match children to day-care places.

In Hungary, to match students to schools.

In New York, to allocate rabbis to synagogues.

And in China, Germany and Spain, to match students to universities.

Whilst in the UK, it's led to the development

of a matching algorithm that, for some people, has saved their lives.

At the age of 20, Seraya in south London was diagnosed

with a chronic kidney disease and told she needed a transplant.

I was on dialysis for 18 months and very unwell.

I couldn't go to work. I had no social life.

It was literally hospital three times a week for treatment and home.

A close friend was willing to donate,

but their tissue types were not compatible.

In St Albans, Tamir was seriously ill

and his wife, Lyndsey, wanted to donate.

But they had the same problem.

We went through all the blood tests and all the workup

and it turned out that we were incompatible blood groups.

Often, kidney patients who are fortunate enough

to have a would-be donor find there's a mismatch

between their donor's blood group or tissue type.

But since 2007, the NHS has been using a special matching algorithm

to find potential matches for willing donors

to kidney patients all over the UK.

When we first looked at this problem,

we really underestimated the complexity.

And originally, we just started with swaps between two pairs.

So it was very simple,

but it soon became obvious that we needed something much more complex.

I became in touch with Rachel Johnson at the NHS

and we then got involved at that stage in being able to design

algorithms which would allow not just pair-wise exchanges,

but also exchanges among three couples, as well.

The algorithm considers several scenarios.

The simplest is a two-way swap

with two couples exchanging kidneys.

More complicated is a three-way swap,

where the kidneys get passed around in a cycle.

There are 200 patients in each of our matching runs.

We need to look for all the possible transplants.

And it's surprising how many there are.

There are literally, you know, hundreds,

sometimes thousands of possibilities.

It's something that just could not be achieved without the algorithm.

One day, Seraya received the call that a match had been found

400 miles away with Linda, a donor living in Bowness near Edinburgh.

My husband's dad needed a new kidney.

He'd been ill for a bit of time. And I wasn't a perfect match.

And I then got a phone call and it was all go from there.

We got the initial phone call saying

we'd been matched up in the three-way pool.

You're just nervous that it's not going to go ahead

because your life depends on it.

For the matching couples,

all the operations had to happen simultaneously.

It was a major logistical challenge.

When my donor went to theatre, they called over to check

that my donor was also in Newcastle going to theatre.

And they both got it at the exact same time.

And they make the call and the kidneys come out.

I think they went by motorbike.

We were told they might go by helicopter,

so I thought at least one bit of me might have been in a helicopter,

but, no, it went by motorbike.

And it eventually went ahead, thankfully, in December.

- The best Christmas present. - Hm!

Personally, I just imagined it was doctors behind there

matching people up off this list.

So, yeah, it's a bit strange

that it comes down to maths at the end of the day.

It's a great scheme and it's still fairly recent.

And many years ago, I wouldn't have had this chance.

I feel a lot of gratitude to Linda and also to the algorithm.

So, yeah, I'm very grateful.

So far, more than 400 patients have benefited from the NHS scheme

and its special matching algorithm.

It was only when we actually seen media articles

and we actually started to think, "Oh, hold on,

"that person might have actually had that match

"through the October matching run's pair-wise exchange," and so on,

that you actually start to see the stories

that are behind the anonymous data.

It's quite funny because David's always really concerned

that the algorithm will take a long time to run.

And, you know, it's been up to 30 minutes and he gets concerned.

But actually, 30 minutes, you know, to us,

it's incredible that it can do all of that in 30 minutes.

So far, we have seen how algorithms are capable of amazing feats.

From solving abstract mathematical problems

to helping us find stuff on the World Wide Web.

And they key thing for all of these algorithms is their speed.

So the important feature of a good algorithm is first

that it'd better be correct, but once you know it's correct,

it's also important that it runs quickly.

There's no good having an algorithm that takes longer

than your lifetime to run if you're wanting the result tomorrow.

This face-detection algorithm is an example of an efficient algorithm.

Because it's efficient, it's able to run in real time.

And that's what makes it useful.

But just as in real life, some problems are harder than others.

Every now and then, algorithms meet their match.

I think the most common misconception about algorithms

is just that algorithms can do anything.

I think people don't really know about the limits.

Some problems simply cannot be solved by efficient algorithms.

There are some places where efficient algorithms cannot go.

Lines in the sand that can't be crossed.

The trouble is knowing which problems they can solve

and which they can't.

Take this Rubik's Cube and imagine the more general challenge

of trying to solve a cube of arbitrary dimensions.

So, for example, with 50 squares down each side.

Now, you might expect this

to be one of the really fiendishly difficult problems,

but actually, it belongs in the easy camp.

We know an algorithm that can solve the general Rubik's Cube

in a reasonable amount of time.

Although it looks hard,

this problem can be cracked by efficient algorithms.

However, here's one that definitely can't.

Imagine you've got a draughts board of arbitrary size

and an arrangement of pieces on the board.

The challenge is to work out

whether white can force a win from this position.

Now, draughts is a pretty easy game,

but it's been mathematically proven

that there's no algorithm that can solve this problem efficiently.

It's an inherently difficult problem.

The only way to solve this puzzle is through sheer hard slog -

working out all the millions of possibilities.

So this problem lies firmly beyond the reach of efficient algorithms.

It can't be solved quickly.

But for some problems, how hard they are is not clear cut.

This is a large sudoku. It's got 625 squares.

One of the nice things about sudoku is that once you've found a solution,

it's relatively straightforward to check whether or not it's right.

And this is true however large the puzzle.

In this case, I've just got to check each row,

column and block doesn't feature a number twice.

Sudoku belongs to a very special category of problems

that all share this characteristic.

Once you've come up with a solution, it's always easy to check it.

The mystery is whether there's an efficient algorithm

to find the solution in the first place.

And sudoku is not alone. There are lots of problems like this.

The most intensely studied of them all

is known as the travelling salesman problem.

A travelling salesman travels door to door, city to city,

selling anything from brushes and Hoovers to double-glazing.

It sounds like a straightforward job.

But all travelling salesmen face the same question.

What's the shortest route to take?

So important is this problem that the Clay Mathematics Institute

has offered 1 million for whoever can find an efficient algorithm,

or prove that none exists.

The travelling salesman problem goes like this.

Imagine you're a salesman

and you've got to visit a list of cities represented by the red dots.

The challenge is to find the shortest route

so you visit each city once before returning to your starting point.

Now, you might imagine the best thing is

to just consider all the routes, like this.

The method of checking all possibilities is a type of algorithm.

And for three cities, it works fine

because there are only three possible routes to check.

But what if we add two more cities to the list?

With five cities, there are 60 different possible routes.

And if we add another city, then there are 360 possible routes.

And for ten cities, there are over 1.8 million possible routes.

If our algorithm chugged through them,

checking all of these at a rate of ten per second,

it would take two days before it found the shortest.

So you can see a method of trying all the different possibilities,

a kind of brute-force algorithm, if you like, is just simply impractical.

If somebody found a fast algorithm for the travelling salesman problem,

it would be hugely significant.

If one of my students came up with an efficient algorithm

for the travelling salesman problem,

I would get him to explain it to me,

I would kill him and then I'd go and claim

the Clay prize, 1 million.

But I think my students are safe.

The problem crops up in lots of areas.

From soldering circuit boards...

..to planning the routes for supermarket deliveries.

But has the travelling salesman problem secretly already been solved?

A team of scientists working at Rothamsted Research in Harpenden

have turned to nature to see if it has found the answer.

They're carrying out an elaborate experiment to study

how the travelling salesman problem is tackled by the bumblebee.

Bees have to forage for nectar in order to provision their hive.

And so they have to visit

possibly hundreds of flowers on each trip.

What they want to do is find an efficient way

to go between all these flowers that they visit.

The humble bumblebee faces its own travelling salesman problem.

The flowers are just like the cities.

And the bee is the travelling salesman.

One bee will go out foraging many, many times every day.

So over the course of a day,

it really helps to take the most efficient possible route.

So what we're doing is trying to figure out

exactly what rules they're using to narrow down the possibilities.

Joe has laid out five feeders which play the role of flowers.

Each feeder has just enough nectar to ensure the bee has to visit all five

to give it a full honey stomach.

And how are you actually knowing where it's going?

For this, we're using a harmonic radar.

So as that spins round and round, it's emitting a radar signal.

And we've attached a small antenna to the back of the bee,

which then reflects the signal from the radar.

And so this allows us to see exactly where the bee has gone

as she moves around the field.

So, how does the bumblebee tackle the travelling salesman problem?

OK, we're switching it on now.

With five feeders, there are a total of 60 possible routes.

The shortest is around the outer edge.

This heat map shows the path taken by a single bee.

At first, it's simply discovering the positions of the feeders.

Then the bee appears to methodically change different parts of the route

to see if it can make it shorter.

Within 20 trips, it's honed in on an efficient route.

This route is not always the absolute shortest,

but, for the bee, it's good enough.

That's amazing that just after a very few tries, they've got

to something which is efficient enough for them to do their foraging.

Yes, that's right. They can't spend days or even, you know,

it could take months or years to try every possibility.

So they have to very quickly find a route

that they can do again and again and again

- in order to efficiently provide food. - Fantastic.

I think the bee's become my favourite insect now.

- It's obviously a mathematician at heart. - Absolutely.

Let's be clear. Bees are not about to be awarded 1 million.

They've not miraculously solved the travelling salesman problem

because they don't always find the shortest route.

But their algorithm is a clever approach.

In maths, it's known as heuristics.

Algorithms that are efficient, that don't find the perfect solution,

but get as close as they can.

The same heuristic approach

has been used to develop an algorithm for Heathrow airport.

DISPATCHER: 'Clear for takeoff...'

Heathrow handles over 1,300 flights a day.

It's Europe's busiest airport.

'..430 clear for takeoff. Surface wind 247 degrees at three knots.'

The challenge for air traffic control

is to maximise the number of aircraft departing every hour

and ensure that the airport operates both efficiently and safely.

'..behind the British Airways 747, line up 27 right behind.'

One of the key decisions is the order of takeoff.

We're currently departing a group of medium aircraft,

which will be separated one minute apart.

Behind that, then, you can see a 747, which is a large aircraft.

Medium aircraft need to be separated from the turbulence

produced by larger aircraft.

So the ordering of sizes is crucial.

The ideal sequence for takeoff involves

really blocking together groups of aircraft.

So you want large aircraft to be grouped together,

medium aircraft to be grouped together.

And that allows the separation

between those aircraft to be minimised.

The other factor that needs to be considered where planning takeoff

is where the planes are heading.

We want one to be going to the north, one to the south,

the next going to the north, then the south.

If all the aircraft were going in the same direction, the separation would be much greater

and we wouldn't use the runways as efficiently.

All controllers are sitting in the control towers thinking,

"I've all these aircraft going north, all these going south.

"I've got these that are large ones,

"so I want to try and group all the large ones together

"so I don't have to go from a large one to a small one."

And it's a very complex problem to solve in their heads.

'..906 November...'

In 2013, an algorithm joined the team.

Its job is to predict the most likely order for takeoff

and advise air traffic control

when aircraft should push back from the gates.

To do this involves nothing less than simulating

the entire outward-bound operation of the airport.

Carrying out millions of calculations every second.

FAINT DISPATCHER

The algorithm works by trying to predict

what order the aircraft are going to take off in.

If it knows what order they can take off in,

then it can work backwards and say,

"If it needs to take off at this time,

"then it needs to enter the runway queue at this time,

"then it needs finishing its taxi at this time,

"so it needs to start its taxi operation at this time.

"In that case, it needs to finish its pushback by this time,

"so it needs to start its pushback by this time."

And it can work all the way back from what time it should take off

to what time it should start pushing back.

The output of the algorithm is given to air traffic control

through the airport's internal computer system

and displayed to the pilot at the gate in the form of the TSAT,

the recommended pushback time.

The pilot can look on the stand-entry system

to actually see what time he is expecting to depart.

The biggest benefit of the algorithm is that it means you can

hold aircraft on stand for longer without them taking off any later.

So there's no loss for any passengers in terms of delays.

What you can do is you can start your engines later.

In actual fact, if we save two minutes' taxi time

on the way to the end of the runway, over a year,

that's actually A�15 million worth of fuel savings.

The Heathrow sequencing algorithm shows just what can be accomplished

with the heuristic approach.

Just like the bees, the algorithm is not finding

the absolute perfect solution all the time,

but nevertheless makes a tough job that bit easier.

We're very proud of the algorithm

because it actually now, we feel, models the real world and is of use.

In the beginning, algorithms were created

by mathematicians for mathematicians.

And over the last century,

algorithms have been created for computers.

But perhaps our relationship is about to go through a dramatic revolution.

At Microsoft Research in Cambridge,

scientists are using new techniques to develop algorithms...

blurring the boundary between inventor and the algorithm itself.

This is the Kinect skeletal-tracking algorithm.

The amazing thing is that it's able to identify

the different parts of my body.

So you can see it's coloured the top of my head in red

and my right hand here in blue.

You can see it's coloured my neck green.

Now, this algorithm has never met me before,

doesn't know how I'm going to move in space,

but just using the data coming from this special camera here,

measuring the distance from the camera to my body,

it's able to produce this map.

Whatever posture I take, using nothing more than the input

from the special depth-sensing camera,

the algorithm is able to accurately identify,

pixel by pixel, the different parts of my body.

It was developed for the Microsoft Xbox console

to track the movement of a player's body posture in real time.

But just as remarkable as what this algorithm can do

is the process behind how it was created,

as researcher Jamie Shotton explains.

What's happening is that every pixel in the image,

we are running an algorithm called a decision tree.

And you can think of a decision tree as a game of 20 questions.

So the decision tree is sort of taking a pixel, say, on my hand,

and trying to decide, OK, I've got to colour that blue

- because that's on the hand rather than on my body. - Yes.

The key to a decision tree is the fact that the 20 questions

that you ask are not the same

for every pixel that we're trying to classify.

And the full set of the possible questions

that could be answered is exponential.

- It's two to the twenty. - Right, OK. That's over a million questions,

a lot of questions you're going to have to program in there.

Yes. It would take far too long

and be far too error-prone for us as humans to program that by hand.

- So, the algorithm's kind of writing itself, or...? - Absolutely.

The algorithm was not designed by Jamie

but instead through a process called machine learning.

It involved showing the algorithm millions of training images,

of bodies in different poses and of various shapes and sizes,

from the very fat to the very thin, the very short to the very tall.

And from this, the algorithm essentially learned by example,

devising its own rules.

Where our intelligence comes in as the designers of the system

is not in programming the algorithm, per se,

but in designing the training data set

to capture all of the kind of variations that we expect to see

when we deploy this system in people's living rooms

to play their games.

So in the end, do you actually know what the algorithm is doing?

We can get a sense of what it's trying to do

and how it's roughly working,

but we couldn't possibly really understand what exactly is going on.

The same approach of machine learning has been used in other applications.

For example, this algorithm is able to do something that for a long time

was thought to be a skill exclusive to neurosurgeons and radiologists.

From an MRI scan, the algorithm can identify

and map a brain tumour in 3-D.

Meaning that a job that normally takes an hour

can be done in a matter of minutes.

Professor Chris Bishop is interested in developing

the concept of machine learning even further.

To create algorithms that can learn just like we do,

directly from experience.

So this demonstration, I think, illustrates the direction

that algorithms will go in the years ahead.

OK, I can see a lot of films up here, so what is the algorithm going to do?

We've got a couple of hundred of the most commonly watched films,

and what it's going to do,

it's going to learn about your personal likes and dislikes.

It's already been trained,

so it's a machine-learning algorithm behind the scenes,

but it's already been trained on data from about 10,000 people.

What it's going to do now is to learn about your preferences.

At the moment it knows nothing about you,

so these films are just arranged at random on the screen.

What I need you to do is to find one of these films,

either one that you like or one that you don't like.

If you like it, you can drag it across to the green region,

if you don't like it, across to the red region.

Rushmore, I'm a big fan of Rushmore.

You like Rushmore? OK, right.

So what's happening now is that if a film is down the right-hand side

- near the green region, it's very confident you'll like it. - OK.

So down here close to the red region,

it's very confident you won't like it.

In the middle, it's 50-50. It doesn't really know.

So if I choose a movie in the middle here,

I'm not a great Austin Powers fan, so let's shoot that one...

So you see, they're beginning to spread out sideways,

- it's going to be a little bit more confident. - It's pretty good.

I'm a big fan of Dr Strangelove

and I'm a big fan of Woody Allen,

but Spinal Tap, it thinks I'll like that.

So that's interesting, so when it was confident you liked them

and you said you liked them,

not much happened because it didn't learn much.

When it was confident you'd like it, in the case of Spinal Tap

and you said, "I don't like it," there was a big change.

It's learning things from me.

I'm actually changing the algorithm as I interact with it.

Exactly. Whereas Kinect was trained in the laboratory and then frozen,

this algorithm continues to adapt

and continues to evolve throughout its life.

The more films that you rate as like and don't like,

the more it knows about you personally

and the better able it is to make good recommendations.

This algorithm is beginning to feel much more human

in the way that it interacts with the world.

Is that your aim, to find a way to produce algorithms

that are a bit like the way that we negotiate the world?

Exactly. It's a step down that very long road to producing machines

that really are as capable as the human brain.

We've a long way to go, but this is a small step in that direction

because it's not fixed any more.

It's now continuing to learn just the same way

that we continue to learn in our daily lives.

I think we're just starting

to realise the full potential of algorithms

and I have one more place I want to visit,

which I'm told will give me a glimpse

of just how much they are able to do for us.

It's a world where almost everything is automated.

Where algorithms are in control.

It's the largest automated grocery warehouse on earth.

It belongs to the online grocery retailer Ocado

and it's the equivalent of 45 supermarkets in one.

Over two million items flow through this warehouse every day.

At any one time, there are something like 7,000 crates

going over 25 kilometres of track,

and controlling every aspect of this astonishing spectacle are algorithms.

Each of those red crates is part of a customer order

and they may go on from here to find other items

that they want across the warehouse,

until they are eventually finished,

loaded onto a van and then driven out by our routing system

on a route, which in many ways,

is solving problems like the travelling salesman problem.

There are decisions being made all over the place

as a red crate goes this way and then that way.

The complexity behind all this is beyond

what any human could control or solve,

and that is where these algorithms,

these problem-solving techniques come in

to overcome those challenges.

Everywhere you look, the invisible hand of the algorithm is at work.

Forecasting algorithms monitor and replenish the stock

of more than 43,000 products, anticipating customer demand.

Control system algorithms manage the traffic

of the more than 7,000 crates around the warehouse.

And van routing algorithms control the movement of the fleet

of over 1,500 vans,

testing over four million different route combinations every second.

You can almost see the mind of the machine at work

and it's not a static process, so that's why there is a huge amount

of machine learning in here, so it's like a self-adapting organism.

It's constantly having to learn how to do it better.

People couldn't do that.

The machine has to tune itself.

So who would you say was actually in control of the whole thing?

Ultimately, it's the algorithms that are in control.

I think I'm getting algorithmic hot flushes

by looking at this amazing thing!

In some sense, this warehouse is like

a little microcosm of the modern world.

Algorithms are running everything from search engines on the internet,

sat nav, even keeping our credit cards secure.

Our world wouldn't function without the power of these algorithms.

The Open University have produced a free pack for you to learn,

create and discover more about digital technology past and present.

To order your copy, phone...

..or follow the link below

to the Open University.