What is an algorithm?

In brief

Article summary

In this article, we present you what are algorithms, and how they can be written and compared. In addition, we present you the concept of pseudo-code, and show a first example of an algorithm.

Main takeaways

• An algorithm is a solution to a specific problem that takes a set of values as input and produces a value as a result. This solution is realised by a sequence of algorithmic statements applied to the input data to produce the final result value.

• Algorithms can be compared according to many criteria.

• Algorithms can be written in pseudo-code, or directly in a programming language.

Article contents

1 — What is an algorithm?

Here is a possible definition of an algorithm:

An algorithm is a solution to a specific problem that takes a set of values as input and produces a value as a result. This solution is realised by a sequence of algorithmic statements applied to the input data to produce the final result value.

Obviously, there can be variations of this definition, as technologies evolve (e.g., quantum algorithmics), but the definition above covers most cases.

Algorithms have existed for centuries, and were used long before the modern computer to describe how problems should be solved. For instance, following a recipee to create a cake is exactly the same as following an algorithm. In other words, it gives you specific instructions that, if you apply them in order, produce the solution you want.

We call specification of an algorithm the type and number of values taken as input, and the expected properties of the output value.

2 — Comparing algorithms

For a given problem, several algorithmic solutions can be generally considered. These candidate solutions which produce the same output for the same set of input values can then be compared according to:

• The complexity (of their understanding).
• The time they take to produce the output value.
• The memory space they require during processing.
• The potential dependence on external algorithms.
• Their use of randomness or not.
• Many other criteria (e.g., need for particular devices).

A classic example of problem that can be solved automatically by algorithms is to take a set of values as input and to reorder them according to an ordering relation. It is an usual problem in an algorithmics course because this task occurs frequently in many application contexts and because several algorithmic strategies can be used to obtain a same ordered set of values. In this course, you will implement and design algorithms for different problems, characterised by their properties, the strategy used or the type of the data on which they are applied.

3 — Languages and algorithms

Algorithmic concepts are often illustrated and manipulated using so-called pseudo-code, a syntax restricted to algorithmic statements with a less rigorous form than formal programming languages. Typically, a pseudo-code could look like this:

total <- 0
for each element l_i in list L do
    total <- total + l_i
done

total := 0
for l_i in L do
    total := total + l_i
done

total <- sum_of_all_elements(L)

# L is supposed to be a list of integers, declared elsewhere
total = sum(L)

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // L is supposed to be a list of integers, declared elsewhere
        int total = 0;
        for (int l_i : L) {
            total += l_i;
        }
    }
}

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

import java.util.Arrays;
import java.util.Arrays;

public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // L is supposed to be a list of integers, declared elsewhere
        int total = Arrays.stream(L).sum();
    }
}

As you can see, the main goal of a pseudo-code is to quickly write an algorithm without focusing on the details of programming languages (types of variables, syntactic constraints, etc.). A pseudo-code can also be a mathematical formulation. For instance, the following is equivalent to all codes above:

To avoid having to learn different formalisms, we have chosen to use the Python programming language in this algorithmic course. Its refined syntax makes it easy to understand, even for beginners. In addition, we will also provide you, as much as possible, with the Java version of the algorithms, for you to familiarize with a second language.

# Input values
S = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
v = 7

# Perform the check
found = False
for s in S:
    found = s == v
    if found:
        break

# Display the result
print(v, 'in', S, ':', found)

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

import java.util.Arrays;

public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Input values
        int[] S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        char v = 7;

        // Perform the check
        boolean found = false;
        for (int s : S) {
            found = (s == v);
            if (found) {
                break;
            }
        }

        // Display the result
        System.out.println(v + " in " + Arrays.toString(S) + " = " + found);
    }
}

# Input values
S = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
v = 7

# Perform the check
found = v in S

# Display the result
print(v, 'in', S, ':', found)

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */

import java.util.Arrays;

public class Main {

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Input values
        int[] S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        char v = 7;

        // Perform the check
        boolean found = Arrays.stream(S).anyMatch(s -> s == v);

        // Display the result
        System.out.println(v + " in " + Arrays.toString(S) + " = " + found);
    }
}

To go further

Looks like this section is empty!

Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!

To go beyond

Looks like this section is empty!

Anything you would have liked to see here? Let us know on the Discord server! Maybe we can add it quickly. Otherwise, it will help us improve the course for next year!