Algorithms and their representation¶

Algorithm - definition¶

Algorithm is a recipe for solving a computational problem.

More professionally, an algorithm can be defined as a sequence of operations carried out with the use of various data structures to solve a programming problem.

In this section, everything will revolve around a thorough understanding of how to describe and create algorithms.

Procedure¶

Below are the steps - from start to finish - to be taken to create a solution (algorithm) for a given problem.

1. Problem/task formulation - we start with determining what problem the algorithm should solve.
2. Determining the input data - what we expect, what we should get as input, what type, values, constraints.
3. Determining the result - what should the algorithm return (the string? List? Function?)
4. Finding a method to perform a task - here there may be several ways to solve one problem (we decide which one is the most suitable for us).
5. Save the algorithm with the chosen method.
6. Algorithm analysis and testing.
7. Assessment of the algorithm's effectiveness - efficiency, simplicity, ease of implementation; let the world know and judge us.

Algorithm representation¶

There are a number of different ways an algorithm can be represented:

• verbal description

The most natural way to present the solution - verbal one. It is the transmission of information about the algorithm begins.

An example of an "algorithm" that is actually a recipe for a hard-boiled egg:

1. Pour water into the pot
2. Put in a pot of x eggs
3. Boil the water
4. Boil the eggs for 8 minutes
5. Pour the water out of the pot
6. Cool the eggs with cold water

• code

The only way to provide information about the operation of the algorithm that you can always be sure. If we tell verbally about the algorithm, it may still be incorrectly conveyed. However, if we want to show the solution using code (certainly a working solution), we can be sure that the code correctly implements and thus describes the algorithm well.

• pseudocode

A way that is something between the previous two. This could still be a written story in principle, but in pseudo-code you should remember about keywords (if - if, else - otherwise, as long as - while, etc.). In addition, you can add code inserts (e.g. x> 5, method calls etc).

• block diagram.

Describing the algorithm for adding three numbers together is simple. But what about verbally conveying information about the operation of the decimal-to-binary algorithm or the calculation of pi number? It is not so trivial anymore and it would be good to find a slightly simpler way, so that after a quick view you could understand and implement the algorithm. Block diagrams are perfect for this.

A block diagram is a graphical representation of an algorithm for the purpose of solving a specific task. On its basis, we set/read the sequence of executed instructions and the flow of the algorithm.

Block diagram¶

Features of block diagrams:

• easy to use - they represent the steps in the algorithm,
• simple structure - a small number of elements (blocks),
• they can be created with the use of syntax notation of any selected language (various operators, e.g. := vs =),
• useful for creating advanced algorithms,
• on their basis, it is much easier to write the code of a given algorithm.

Types of block diagrams¶

There are four types of diagrams:

• simple (sequential),

Conditional blocks are not used in them. In such a flow of activities, the sequence of execution of individual operations is strictly defined and none of them can be omitted or repeated.

Here's the diagram for "Hello, World!" program:

Diagram for a program that calculates the area of the square:

• with separation,

It includes the choice of one of several possible ways to accomplish a given task. There is at least one conditional block in it.

• with loop,

Often, during the implementation of a given task, it is necessary to repeat some operations that differ only in the data set. The loop covers that part of the blocks to be repeated.

• complex.

Being a combination of the above flows. The diagram for the factorial is that of the compound family. It has already been shown before, here is a small reminder (each block marked with a number here will be described later in the material):

Block diagrams - symbols¶

BORDER BLOCKS (no. 1 and 7)

These are oval-shaped blocks that begin and end with the block representation of the algorithm. Only one down arrow comes out of the START block (usually so-called), none of it in. One arrow enters the STOP block (END, etc.), but no more comes out - when the algorithm reaches this block, its execution ends.

Function: to mark the beginning and end of the algorithm.

ARROW/CONNECTOR

The arrow (connector) clearly indicates the direction of the instruction flow - it should never divide, the algorithm should clearly move from one block to another. However, it should be remembered that it is possible to return using the arrow from the block below to the block above (we are dealing then with a loop of the instruction).

Function: indicates the order in which the algorithm executes instructions.

OPERATION BOX (no. 3 and 5)

The operation box is represented by a rectangle. Its interior contains all operations / instructions performed during the algorithm's operation (except for the conditional instruction). In this block you can define a variable, change its value, write some simple command in words (eg "add a letter to the end of the current string").

Function: to store the instructions that should be executed in the given algorithm step.

INPUT/OUTPUT BOX (no. 2 and 6)

Represented in the diagram by a parallelogram, input / output boxes are used to contact the user through commands that print values (e.g. print) or ask the user to enter one (e.g. input).

Function: data input / output.

CONDITION BOX (no. 4)

The conditional box stores selection statements (in a diamond). One arrow enters it, while two come out: for the value YES (when the condition written in the diamond is true) and for the value NO (when it is not).

Function: checking a condition (TRUE / FALSE).

WHILE LOOP

Representation of the while loop: first checking the condition, then executing the statement, finally returning to the point of checking the condition (starting the next iteration in the loop).

DO WHILE (UNTIL) LOOP

Loop representation until (do while): statement first, then condition test (plus potential repeat execution of the statement).

FOR LOOP

Simulation of the for loop: looping the execution of the statement the number of times specified in the diagram; i increased until the value is equal to the max.

Block diagrams for example algorithms¶

Password typing algorithm¶

Algorithm for converting a decimal number to a binary number¶

Algorithm for calculating GCD¶