Branching (Part 3)

Example: three (not twenty) questions

As another example, suppose we're playing a simplified version of the two-player game "twenty questions". Here one player chooses a number in the range 1 to 8 and the other player is allowed three yes/no questions to try to determine the answer. Twenty questions would make it way too easy!

Let's rewrite the questions as conditions. The first one is true when the number is less than 2. The condition, num < 2, splits the possibilities into two cases: the number is 1 if the condition is true and otherwise is one of the other numbers from 2 to 8.

Two categories: 1 and all numbers from 2 to 8.

If the number hasn't been guessed yet, we know that the number cannot be 1, so when we compare it to three, we can split the numbers from 2 to 8 into two pieces, those for which the condition num<3 is true and those for which the condition is false. Remember, for all of these the first condition is false. So the only number which is greater than or equal to 2 and less than 3 is the number 2.

Three categories: 1, 2, and all numbers from 3 to 8.

We can repeat this process to split the numbers up more. But if the first three conditions (num < 2, num < 3, num < 4) are false, then we still do not know whether the number is 4, 5, 6, 7, or 8.

Four categories: 1, 2, 3, and all numbers from 4 to 8.

This is an ineffective way to win the game.

Nested branching

Here's a different way of using branching. In our diagrams using red and blue circles, the blue circles can represent any kinds of instructions, including more branching steps. The first condition splits the cases into two pieces, like before, as shown in figure (1): further branching occur for the cases in which the conditions are true. Branching inside branching is called "nested branching". In "nested branching", we'll use conditions to split both pieces, that is, the cases for which the first condition is true and also the cases for which the first condition is false, as shown in figure (2).

Branching twice splits categories into two sub-categories at each test of the condition. Further branching occur for the cases in which the condition is true. — Fig. (1): Branching twice

Nested branching is branching inside branching. Branching occur for each of the cases when the condition is true and false. — Fig. (2): Nested branching

Three questions with nested branching

Using this idea in our example, we are no longer limited to conditions that break off one case at a time.

We can split the cases more evenly, by using a condition that is true for half of the cases. For this condition, the two groups are numbers less than 5, num < 5, and numbers greater than or equal to 5, num >= 5:

Numbers from 1 to 8 are split into two groups, 1 to 4 and 5 to 8, using the condition num<5.

Now we can split each of the groups with a condition. If we have the first group, we use the condition num < 3, resulting in two sub-groups 1 to 2 and 3 to 4. For the second group, we use the condition num < 7, resulting in two sub-groups 5 to 6 and 7 to 8.

Using the conditions num<3 and num<7, the two groups 1 to 4 and 5 to 8 are each further divided into two groups to get the four groups 1 to 2, 3 to 4, 5 to 6, and 7 to 8.

Now we have four groups: 1 to 2, 3 to 4, 5 to 6, and 7 to 8. The first group, 1 to 2, has numbers for which the conditions num < 5 and num < 3 are both true. The second group, 3 to 4, has numbers for which the condition num < 5 is true, but the condition num < 3 is false. The third group, 5 to 6, has numbers for which the condition num < 5 is false, but the condition num < 7 is true. For the fourth group, both num < 5 and num < 7 are false.

Using the conditions num<2, num<4, num<6, and num<8, the four groups, 1 to 2, 3 to 4, 5 to 6, and 7 to 8, are further divided to form eight groups: 1, 2, 3, 4, 5, 6, 7, 8.

We can choose another condition for each group, to separate them into 8 different cases. This means that different conditions are used in different cases, but for each possible case, three questions are enough to determine the answer.

Visualization of nested branching

Viewing this as red and blue circles, we see that there are eight different sets of blue circles corresponding to the eight numbers, as shown in the figure below. From the top triangle there are two outcomes, each resulting in examining another triangle, and for each of those, again there are two outcomes, each leading to another triangle.

The outcome (true or false) of the single top triangle gives two triangles. The four outcomes of these two triangles give four triangles. The outcome of these four triangles gives eight different sets of blue circles corresponding to the eight numbers.

Visualizing three questions

The set of conditions and instructions after the first condition can be divided into two groups, one (left) of which is executed when the first condition is true and the other (right) executed when the first condition is false. This can be represented visually: the group on the left is for when the first condition is true, as showin in figure (3), and the group on the right for when the condition is false, as shown in figure (4).

The set of conditions and instructions that are executed when the outcome of the first condition is true. — Fig. (3)

The set of conditions and instructions that are executed when the outcome of the first condition is false. — Fig. (4)

If the outcome of the first condition is true, there are two sets of conditions and instructions that are executed depending on the outcome of the second condition: one set (left) is executed if the outcome is true, as shown in figure (5), and the other (right) if the outcome is false, as shown in figure (6). This is similar to the pattern observed earlier: the same structure holds in the left group with respect to the second condition since there is a group for when the condition is true and a group for when the condition is false.

The set of conditions and instructions that are executed when the outcome of the first condition is true and the outcome of the second condition is true. — Fig. (5)

If the outcome of the first condition is true, again, there are two sets of conditions and instructions that are executed depending on the outcome of the second condition: one set (left) is executed if the outcome of the second condition is true, as shown in figure (7), and the other (right) if the outcome of the second condition is false, as shown in figure (8).

The set of conditions and instructions that are executed when the outcome of the first condition is false and the outcome of the second condition is true. — Fig. (7)

If we think of the conditions appearing in three levels, we see that in each course of action, we consider a condition on level 1, a condition on level 2, and a condition on level 3. The condition on level one is the first condition. The conditions in level 2 are the conditions following the first condition but before the next set of condition. The conditions in level 3 are the set of conditions that occur depending on the outcome of the first two conditions. These are shown in figure (9).

For example, let's illustrate the path taken if the conditions encountered are, in order, false, true, and false. The line passes through the upper three red circles and the first triangle turning right (false). Then it to passes through the triangle in level 2 turning left (true). Then it passes through the triangle in level 3 turning right (false) to pass through the associated dashed blue circles and the final red circles. This is illustrated in figure (10).

Conditions in level 1 (first condition), conditions in level 2 (second set of conditions), and conditions in level 3 (third set of conditions). — Fig. (9)

Let's consider the path taken if the outcome of the three conditions are true, true, and true. The path passes through the upper red circles and the first triangle turning left (true). Next, it passes though the triangle in level 2 turning left again (true). Then it passes through the triangle in level 3 turning left (true). Next the path passes though the leftmost dashed blue circles and the last set of red circles. This is illustrated in figure (11).

The path taken if the conditions encountered are, in order, true, true, and true. — Fig. (11)

Pseudocode for nested branching

if guess < 5 if guess < 3 if guess < 2 correct ← 1 else correct ← 2 else if guess < 4 correct ← 3 else correct ← 4 else if guess < 7 if guess < 6 correct ← 5 else correct ← 6 else if guess < 8 correct ← 7 else correct ← 8 print(correct)

How do we write this as pseudocode? Each of our splits are into two, so we use if to introduce the course of action when the condition is true and else to introduce the course of action when the condition is false. Here are the lines associated with the first condition. There are more lines on the next page for the course of action when the condition is false. For now, let's focus on what happens when the number is less than 5. We next check the condition guess < 3. Here are the lines that split up the cases for which it is true and those for which it is false. When it is true we have another split, each case letting us determine the correct answer and also when it is false. The pseudocode for all of the branching is given on the right.

You can see that the same pattern holds for the larger half of the numbers: Here is where the condition guess < 7 is checked and the cases split, those for which the condition is true are split again using the condition guess < 6, and those for which the condition is false are split again using the condition guess < 8.