Understanding Algorithms: A Step-by-Step Guide

In programming, the word "algorithm" might sound scary.

But it really isn't.

It's a set of instructions or a step-by-step procedure used to solve a problem or accomplish a task.

Let's see, for example, the "Divide et Impera" (Ancient Romans applied this to military strategy!)

— Francesco (@FrancescoCiull4) March 18, 2023

This thread is inspired by a lesson from the "Computer Science Fundamentals" by @brilliantorg, a platform that teaches Mathematics, Computer Science, and more.

Lessons are bite-size and interactive to help you learn.

Check it out for free at https://t.co/xaHSNNArQQ pic.twitter.com/rid6AxPdpu

— Francesco (@FrancescoCiull4) March 18, 2023

In 20 Questions, one player chooses an object or a famous person, while the other asks up to 20 yes-or-no questions to try to guess the object.

If the questioner correctly guesses the object within 20 questions, they win.

— Francesco (@FrancescoCiull4) March 18, 2023

What strategies can the questioner and computer use in a simpler 20 Questions version with 200,000 Wikipedia performers?

One strategy is to ask random yes-or-no questions about actors, such as:

"Is it Obama?"

or

"Is it Jackie Chan?"

— Francesco (@FrancescoCiull4) March 18, 2023

20 Questions is limited to 20 questions to avoid the game taking several weeks to complete.

Listing the top 20 famous people is unreliable as the answerer might think of someone less known.

One-by-one guessing is only advisable when there are at most 20 choices.

— Francesco (@FrancescoCiull4) March 18, 2023

In 20 Questions, the questioner can ask about multiple traits, such as where they live or their hair color.

Asking "balanced" questions that divide people into similar-sized groups is effective.

This technique, known as "divide et impera" is widely used in computer science.

— Francesco (@FrancescoCiull4) March 18, 2023

By Wikipedia, there are ~200000 actors.

The questioner aims to ask a question that eliminates many actors/actresses from the list of 200000 on Wikipedia, regardless of whether the answer is "Yes" or "No."

A visual representation: pic.twitter.com/of1HFNXk10

— Francesco (@FrancescoCiull4) March 18, 2023

Asking if the actor is male is an excellent way to divide the candidates into ~half.

Asking if the performer is Indian may also narrow down the field, but not by much.

Asking if the performer played James Bond is not helpful since only a few have played that role.

— Francesco (@FrancescoCiull4) March 18, 2023

Animated game of 20 Questions with the answer "Janelle Monáe".

Questions divide the remaining group of performers in half, and eliminated performers are shown in grey. pic.twitter.com/55l0aRoT3e

— Francesco (@FrancescoCiull4) March 18, 2023

Graph of a game of 20 Questions with questions on the horizontal axis and the number of remaining performers on the vertical axis. pic.twitter.com/jOvKCDx154

— Francesco (@FrancescoCiull4) March 18, 2023

The graph becomes more evident if the vertical axis is logarithmically scaled to represent the number of actors.

The initial performers correspond to a bit less than 18 on the vertical axis. pic.twitter.com/ACL3v5xYWr

— Francesco (@FrancescoCiull4) March 18, 2023

Each question in the game of 20 Questions tries to balance the number of performers eliminated by a "Yes" or a "No"

This ensures the questioner can rely on something other than luck to eliminate many performers or risk ending up with only a tiny fraction of the original number pic.twitter.com/BqPw1lyZ2P

— Francesco (@FrancescoCiull4) March 18, 2023

Here is another graph:

Asking questions that perfectly divide the candidates in half results in a graph with a nearly straight line. pic.twitter.com/zlvda0NBZZ

— Francesco (@FrancescoCiull4) March 18, 2023

Consider breaking away from the perfect balance of questions if prior knowledge about the answerer's preferences exists.

If the answerer is a Bollywood fan, ask if the performer is an Indian citizen.

But the answerer may anticipate this and avoid choosing an Indian citizen.

— Francesco (@FrancescoCiull4) March 18, 2023

Simulating 20 games of 20 Questions with 50-50 splits produces similar results, but the games are different.

The number of answers might vary from 16 to 19

Why? pic.twitter.com/Bq71mV9XzB

— Francesco (@FrancescoCiull4) March 18, 2023

Imagine a small guessing game with three possibilities:

The first question can only split into one group of 1 and 2.

You can guess the answer immediately if the performer is in the smaller group, otherwise you'll need one more question to determine the answer.

— Francesco (@FrancescoCiull4) March 18, 2023

Another strategy besides asking 50-50 questions is to ask 25-75 questions.

These questions split the candidates into one group with 25% and another with 75%, for example, dividing 200,000 performers into groups of 50,000 and 150,000.

— Francesco (@FrancescoCiull4) March 18, 2023

Taking this idea to the extreme won't work.

You'd be back to picking out individual performers and asking about them, the strategy rejected earlier.

25-75 questions can lead to lucky guesses that dramatically reduce the number of candidates but often leads to unlucky guesses.

— Francesco (@FrancescoCiull4) March 18, 2023

Splitting the candidates in half with 50-50 questions makes the game more consistent and faster.

Asking 25-75 questions can result in a worst-case scenario of 39 and a best-case of 9 questions to find one performer out of 200,000.

On average, it takes 21.2 questions.

— Francesco (@FrancescoCiull4) March 18, 2023

The graph shows how different question balances affect the worst case, best case, and the average number of questions needed to identify one out of 200000 possibilities.

Asking 50-50 questions results in 18 questions in the worst case, 17 in the best case, and 17.7 on average. pic.twitter.com/XYA9ibiAxr

— Francesco (@FrancescoCiull4) March 18, 2023

This proves how using 50-50 splits in 20 Questions is the most consistent and efficient strategy if you have no extra information about your opponent's guess or if you value a consistent number of questions.

— Francesco (@FrancescoCiull4) March 18, 2023

Conclusion:

The "divide et impera" strategy in computer science can be applied in the game of 20 Questions.

Asking 50-50 questions that divide the group of candidates most evenly is the most consistent and fastest strategy, even though there are other ways to play the game.

— Francesco (@FrancescoCiull4) March 18, 2023

As I mentioned, this was taken from @brilliantorg 's course on Computer Science.

If you're going to succeed in tech, it's crucial that you understand these topics, and Brilliant will help.

Get 30 days free + 20% off an annual plan with my link: https://t.co/xaHSNNArQQ

— Francesco (@FrancescoCiull4) March 18, 2023