Algoritmics with Rust

Originaly posted on my blog.

Hello, today we are going to talk about Algoritmics!

"Algoritmics? Is it eatable?"

Hell no, or only by your brain. Before speaking about algoritmics, let's talk about algorithm. According to Wikipedia:

In mathematics and computer science, an algorithm (ⁱ/ˈælÉ¡É™rɪðəm/ AL-gÉ™-ri-dhÉ™m) is a self-contained sequence of actions to be performed. Algorithms can perform calculation, data processing and automated reasoning tasks. An algorithm is an effective method that can be expressed within a finite amount of space and time^[1] and in a well-defined formal language^[2] for calculating a function.^[3] Starting from an initial state and initial input (perhaps empty),^[4] the instructions describe a computation that, when executed, proceeds through a finite^[5] number of well-defined successive states, eventually producing "output"^[6] and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.^[7]

This is quite difficult to eat. To put it simply, an algorithm is a sequence of operations which produce a result. For example, when you are baking bread, you follow an algorithm: you're putting the flour, then the yeast, etc... And it produces bread.

And again according to Wikipedia:

Algorithmics is the science of algorithms. It includes algorithm design, the art of building a procedure which can solve efficiently a specific problem or a class of problem, algorithmic complexity theory, the study of estimating the hardness of problems by studying the properties of algorithm that solves them, or algorithm analysis, the science of studying the properties of a problem, such as quantifying resources in time and memory space needed by this algorithm to solve this problem.

We could say that algorithmics is studying and making algorithm. This include calculate the complexity or the cost of them.

"Cost? I got to pay?"

Yes and no. An algorithm got a cost of resources. When you bake your bread, you use ingredients (those are the inputs) and for each action, you use resources (like your hand, a wooden spoon, etc...) and those represent the cost.

What we want is to evaluate this cost, also called complexity.

Again with Wikipedia (yes, again):

In computer science, the analysis of algorithms is the determination of the amount of time, storage and/or other resources necessary to execute them. Most algorithms are designed to work with inputs of arbitrary length. Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).

"So, how do we measure that?"

First, it exists a specific notation: O(f(n)) ("Big O of f(n)") where f is a mathematical function of n.

Look at the following algorithm:

Entries: array a of size n
For i from 1 to n do
  print a[i] // one action here
End for

We got an input array with n elements. For each of the, we are going to print it, so one action. At the end, the algorithm should have print n time. So n actions. So the complexity is O(n).

It does not matter if you make one are two actions, the constant factor is always relative to n.

But in the following algorithm:

Entries: array a of size n
For i from 1 to n do
  For j from 1 to n do
    print a[i] // one action
  End for
End for

We do a second loop inside the first one. So we are printing n messages n times. So the complexity is O(n²).

"Ok, and the Rust"

It is juste the language I have chose to make the future algorithms.

As this article starts to getting big, I shall end it here, see you next for the studying of bubble sort.

-- Mathieu