Algorhitms and algorithmic structures - introduction

• Algorithm – definition and examples
• Alternative algorithms
• Algorithmic structures – linear, branching, and looping

An algorithm can be defined as a procedure with clearly defined steps that lead to the solution of a problem. An algorithm can refer to any process, activity, or problem-solving method. Therefore, we use algorithms all the time in our everyday lives.

Example 1

Let’s say we want to make lemonade. There are specific steps we need to follow in a certain order to accomplish this. It’s a recipe for lemonade but, in an informatics sense, it’s also an algorithm:

1. Take a pitcher and pour one liter of water into it.
2. Take one lemon and wash it.
3. Cut the lemon in half and squeeze it using a juicer.
4. Pour the lemon juice into the pitcher.
5. Add one tablespoon of sugar to the pitcher.
6. Stir the liquid in the pitcher for about half a minute to mix everything together.

In an algorithm, steps are executed in the exact order they are written (in this case, from step 1 to 6). This order is important because if steps are done out of sequence, the desired result may not be achieved.

For instance, if you stir the liquid (step 6) before adding all the ingredients (steps 4 and 5), the sugar may not dissolve properly, and the result won’t be a uniformly flavored lemonade. Also, you can’t pour the lemon juice (step 4) if you haven’t first cut and squeezed the lemon (step 3) and washed it (step 2).

Of course, in real life, there are often multiple ways to reach a solution. There are almost always alternative procedures and steps. Therefore, for every algorithm, there’s usually an alternative algorithm that achieves the same result using different steps or a different order.

Example 2

Some steps from the lemonade-making algorithm above can be rearranged, resulting in an alternative algorithm that still leads to the same outcome. For example, the water can be added toward the end, just before stirring, and the sugar can be added at the beginning. So we get the following alternative lemonade algorithm (by swapping steps 1 and 5 from Example 1):

1. Take a pitcher and add a tablespoon of sugar.
2. Take one lemon and wash it.
3. Cut the lemon in half and squeeze it using a juicer.
4. Pour the lemon juice into the pitcher.
5. Add one liter of water to the pitcher.
6. Stir the liquid in the pitcher for about half a minute to mix everything together.

Any sequence of Java commands written within a method body (a block of statements) actually represents an algorithm (i.e., its implementation in Java).

The Java commands in the examples above are executed strictly in the order in which they are written – “top to bottom”. However, in some situations, it’s desirable to execute certain commands only if a specific condition is met. Other situations may require a command to be repeated multiple times.

Each of these three cases corresponds to a different algorithmic structure:

• Linear (sequential) – each command (step) is executed once, in the order written, unconditionally, and without repetition.
• Branching (selection) – a condition is checked first; if it is true, one set of commands is executed; if not, a different set is executed.
• Looping (iteration, cyclic) – a command (or a group of commands) is executed multiple times in a row.

The algorithms from Examples 1 and 2 are purely linear structures, with no branching or looping. They don’t contain any conditions, decisions, or repeated steps. The next example introduces the concept of a branching structure.

Example 3

Let’s say that the lemonade-making algorithms from the previous examples aren’t good enough because they don’t take into account that the lemonade should be tasted and possibly sweetened further if it’s not sweet enough.

If we want to taste the lemonade to check if it’s sweet enough, and then add more sugar if necessary (or do nothing if it is sweet enough), we’re introducing a branching structure (decision-making) into the algorithm. After this change, the algorithm would look like this:

1. Take a pitcher and pour one liter of water into it.
2. Take one lemon and wash it.
3. Cut the lemon in half and squeeze it using a juicer.
4. Pour the lemon juice into the pitcher.
5. Add a tablespoon of sugar to the pitcher.
6. Taste the lemonade. Is it sweet enough? (CONDITION for branching)

• BRANCH_YES: Do not add anything.
• BRANCH_NO: Add one more tablespoon of sugar.

7. Stir the liquid in the pitcher for about half a minute to mix everything together.

Note that BRANCH_YES will be executed only if the condition is met, i.e., the lemonade is sweet enough. BRANCH_NO (adding another tablespoon of sugar) will only be executed if the lemonade is not sweet enough. Both branches are never executed at the same time.

After these changes, this algorithm now contains both a linear and a branching (selection) structure.

The next example explains the concept of a looping structure. As mentioned earlier, there are cases where certain steps need to be repeated, and looping algorithmic structures are used in such situations.

Example 4

Let’s say that the lemonade-making algorithm from the previous example still isn’t quite right, and instead of adding just one tablespoon of sugar before tasting, we want to add three tablespoons first.

The simplest way to write the algorithm is to repeat step 5 three times, like this:

1. Take a pitcher and pour one liter of water into it.
2. Take one lemon and wash it.
3. Cut the lemon in half and squeeze it using a juicer.
4. Pour the lemon juice into the pitcher.
5. Add a tablespoon of sugar to the pitcher.
6. Add a tablespoon of sugar to the pitcher.
7. Add a tablespoon of sugar to the pitcher.
8. Taste the lemonade. Is it sweet enough? (CONDITION for branching)

• BRANCH_YES: Do not add anything.
• BRANCH_NO: Add one more tablespoon of sugar.

9. Stir the liquid in the pitcher for about half a minute to mix everything together.

But what if this step needs to be repeated fifty times or until a certain condition is met? Simply copying the step would make the algorithm unreadable (in the first case) or unworkable (in the second case) if we don’t know in advance how many times it needs to repeat.

A better solution is to introduce a looping algorithmic structure that repeats a step multiple times until a condition is met. With that change, the algorithm would look like this:

1. Take a pitcher and pour one liter of water into it.
2. Take one lemon and wash it.
3. Cut the lemon in half and squeeze it using a juicer.
4. Pour the lemon juice into the pitcher.
5. Counter = 0. Repeat until the counter reaches 3: (loop structure with a counter)

• 5.1. Add a tablespoon of sugar to the pitcher.
• 5.2. Increase the counter by 1.

6. Taste the lemonade. Is it sweet enough? (CONDITION for branching)

• BRANCH_YES: Do not add anything.
• BRANCH_NO: Add one more tablespoon of sugar.

7. Stir the liquid in the pitcher for about half a minute to mix everything together.

Note that step 5 now contains a loop structure with a counter that repeats the action of adding sugar exactly three times. The counter and step 5.2 are part of the loop and control its execution.

This loop works as follows: The counter starts at zero. After each sugar addition (step 5.1), the counter is increased by one (step 5.2). After the first tablespoon, the counter becomes 1. After the second, it becomes 2, and after the third, it becomes 3. The loop stops when the counter reaches 3.

It’s worth noting that this algorithm now contains all three types of algorithmic structures: linear, branching, and looping.

It is common practice for algorithms to include multiple algorithmic structures. Therefore, more complex algorithms are usually created this way: by combining several algorithmic structures (both the same and different types) into one algorithm. The more structures an algorithm has, the more complex it is.

Moreover, these structures are often nested within each other, so you may have a selection structure inside a loop, or vice versa. Sometimes, the nesting is even deeper, making the algorithm increasingly complex.

The next chapter provides an overview of how these algorithmic structures are implemented in the Java programming language, i.e., which Java statements are used to realize them.

Each of these statements is then explained in detail in its own chapter.