You might have heard people talk about algorithms. It’s one of those words that consultants like to throw around a lot. But what are algorithms?
“We’ve developed the worlds most sophisticated algorithm” or “We’re trying to cater for the Google algorithm”… This sounds fancy but what does it mean? After reading this article, you will know more about what an algorithm is than the clever consultants.
The optimal strategy for an algorithm
In this article we will present an algorithm that will reveal the optimal strategy for the popular mid-80s board game “Guess Who?“. When computer scientists talk about algorithms, we’re talking about processes that repeat themselves until they have found a solution. Algorithms have been used for thousands of years to solve problems. The ancient Egyptians developed the first known algorithms for multiplying two numbers. The Greek mathematician Euclid famously developed the Euclidean Algorithm for finding the greatest common divisor of two numbers. Today, we will carve our own piece of history as we shall develop the “Guess Who?” algorithm.
By narrowing down your target, you will eventually know who you are looking for. In the context of “Guess Who?”, an algorithm is a strategy that we can repeat until we’ve found exactly that.
In “Guess Who?”, you are presented with the faces of 20 people. Your opponent has secretly chosen one of these people, and your task is to – you guessed it – guess who. With every turn, you are allowed to ask a single question to which your opponent has to answer (truthfully) yes or no. For example, you could start the game by asking: “Does the person I am looking for wear glasses?”. By narrowing down your target, you will eventually know who you are looking for. In the context of “Guess Who?”, an algorithm is a strategy that we can repeat until we’ve found exactly that.
The Brute Force approach
The first approach computer scientists usually take is the simplest solution they can come up with. Programming computers is difficult and error-prone, and it is often sufficient to use very simple solutions. In the context of “Guess who?”, the Brute Force approach would be to go through each of the 20 people and ask the opponent if the person we are currently looking at is our target. If we are lucky, we might get it right on the first guess. If not, we might have to guess 20 times. If we assume that our opponent pick a person at random, we can expect to make about 10 guesses in an average game. Using the terminology of computer scientists, we would say that we have devised an algorithm that has an expected runtime of 10, and worst-case run time of 20, and a best-case runtime of 1.
Narrowing down with Binary Search
Can we do better? A different approach would be to ask broad questions that divide the group of people into even smaller sub-groups. Asking questions like “Is the person I am looking for male or female?” and “Does the person I am looking for wear a hat?” would quickly shrink the number of plausible candidates.
Asking questions like “Is the person I am looking for male or female?” and “Does the person I am looking for wear a hat?” would quickly shrink the number of plausible candidates.
Let’s assume that we can always come up with a question that divide the remaining possible candidates exactly in half – this is called the Binary Search approach. We would start with 20 possible candidates, then 10, then 5, and then either 2 or 3. After only 3 guesses, we would have a pretty good idea of who the person would be. If we are lucky, we have only 2 people left, and we find our target on our 4th guess. If we are unlucky, we have 3 people left, and we miss on our two first attempts at guessing the target. In that case, we find the person we are looking for on our 6th guess. We say that the best-case runtime is 4 and the worst case is 6. The average runtime is somewhere between 4 and 6 guesses.
What happens when we play a game with even more players?
It might not seem that we’ve accomplished a lot. After all, what’s really the difference between guessing ~10 times or ~5 times? For a computer, the difference between running 10 instructions and 5 instructions is a matter of nanoseconds. However, let’s see what happens if we play a game of “Guess Who?” with more people. The graph below show the number of people on the x-axis, and the average runtime on the y-axis.
The straight line represents the naive approach, while the curved line in the bottom of the graph represents the binary search approach. It should be fairly obvious why the binary search is a huge improvement. As the number of people increases, the runtime almost remains constant. Meanwhile, the runtime of the brute force algorithm increases steadily with the population.
And there you have it. Algorithms are repeated processes that solve problems. And in order to determine how much time it takes to run an algorithm, computer scientists calculate the expected average number of instructions.
If you want to know more about a much-sophisticated algorithm, see our article about Neural Networks.