Algorithmics

Hello world and Charlie, my previous holidays were eventful as I had the chance to participate in my first (and not the least) algorithmic competition in Aix-en-Provence. The competition is called prologin and is probably the most famous (& prestigious !) national french programming contest.

In this article I want to make an introduction to algorithmics so you can further your general knowledge and then share my experience.

What is an algorithm and what is algorithmics?

Algorithmics is the name of the science behind algorithms. An algorithm is exactly like a todo list or a tutorial ; it is made of steps you repeat to obtain a certain result. For example, each time you are cooking using an internet recipe you are indeed processing yourself an algorithm. If one day you decide to buy a cooking-robot, the steps the robot will follow to cook you a selected meal “a” can be called an algorithm to make “a”.

There are a ton of ways to make “a”, as you can reverse the order of certain ingredients or replace some with others, for example butter can often be replaced with olive oil. In this case we could imagine two different algorithms, one using “olive oil” and one using “butter”. Algorithmics explore the different possibilities to make an algorithm for, in this case, make the same recipe faster, tastier, with less or available ingredients.

Of course this case is very trivial and we may not see how an algorithm can be useful in this case, but for larger operations it is absolutely necessary (in the case of a giant automated cookie factory or whatever makes you hungry right now !).

An algorithm typically divides a big problem/task into smaller subproblems/tasks.

The link between Algorithms and Computers

Computer programs are made of multiple algorithms which can be triggered by clicking on a button.

In this case, algorithms follow logical and mathematical operations and conventions have been made for them to be written in comprehensible language. These languages form the main computer programming languages you may know ; Python, Javascript, Java (yep Javascript and Java aren’t the same..), C, C++ and so forth.

There is also one programmation language that take the structure of traditional programming languages but is not readable by computers and is just made to be more comprehensible for humans which is called “pseudo-code” and articulates likes this :

In this very brief pseudo-code program case if case “1” is recognized the program will print “I am case 1” etc

A concrete practical example of this algorithm :

There is no details of how the data of which case “1” or “2” is collected so we can assume that it is an human on a keyboard that type 1 or 2 and the text “I am case [1|2]” is simply rendered on a screen. In the case of our giant automated cookie factory “case 2” can report flaws on our cookies which thus cannot be sold :( .

Now let’s get into the substance of the subject ;)

Dijkstra algorithm of the shortest path

We’re going to dive into a more complex and thorough approach to algorithmics, with the basic problem of the shortest path between a point A & B. These types of algorithms are used in GPS devices or GPS Apps such as Waze or Google Maps. If you’re interested in learning algorithmics I just want you to know that these types of algorithms using “graphs” are never taught at the beginning but rather in the middle of regular algorithmic syllabus. In France, the Dijkstra algorithm is taught to computing bachelor students during their second year.

In this case we want to find an algorithm that gives us the details of the shortest path between the main gates of the Parc Longchamp and the main entrance of the Lycée Saint Charles. 

First thing to do is to transpose the problem to a paradigm the computer can understand. Because it is obvious that a computer cannot decrypt the picture alone. To modelisate this type of problem we use “graphs” which is just a mathematical way to describe certain situations.

The way our graph will be made is simple; each time we are confronted to different choice like going right or going left we will place a “node” so it will look like this ;

(Yes, as you can tell I’m very skilled with paint !) (I didn’t put all the possibilities because it would be too long)

In this graph point A is our starting point and point Z is our destination.

The point is that this is how your GPS Devices or GPS Apps see the map of the world when they want to calculate the shortest path ; each time a decision is possible there is what we call a “node” which is a point with an unique ID (in this case the alphabet letters).

Now there is detail we’ve missed, as we’re trying to find the shortest past we need to give the possibility to our algorithm to have access to the distances between each “node”. This value will be added under a “cost” when choosing a node. So for example when our algorithm will pick “B” from “A” it will cost him 15 meters, when picking “H” from “A” will cost only 10 meters.

From this point we can finally start to imagine the algorithm. We could try to start with a random decision (between B, H, P and O) and see if we arrive at Lycée Saint Charles, then if we arrive we can store the total length of the path (which is the sum of the costs of each decision) and retry a random path until we find smaller. After 10 minutes of random paths trials we can stop the program and return the smallest path in terms of costs we have found.

This algorithm can work but is very critiquable, first because the execution time is completely arbitrary whereas it should be adapted to the longer and possibilities of shortest paths between an origin and a destination (in this case A and Z) and secondly because there will be a ton of duplicated unnecessary operations which are clearly evitable.

Fortunately for the sake of this article, in 1956 Edsger W. Dijkstra in a research paper presented an algorithm to solve this shortest path problem with great efficiency (it is not necessarily the most efficient but for sure the most famous of all shortest path algorithms).

The steps are simple ;

->First we “iterate” (which means look one by one) at all the neighboring nodes of our origin “A” which are B, H, O and P and we sort the paths created in the increasing order of their cost (in meters)

In this case B is the “cheapest” path from “A” with only 5 meters.

The list in order will look like;

1. A->B with 5 meters
2. A->H with 10 meters
3. A->P with 10 meters
4. A-> O with 15 meters

Another list is also updated; the one with the “visited” nodes, which will look like :

-A

->Then for the complementary node (“B”) in the path with the lowest cost (the path “A->B”), we iterate through its neighbors (H, C and D) only if they are not in the “visited” nodes list (for now there is only A so they aren’t) and add the paths to the same sorted by increasing values list.

A->B->H = 5 (A->B) + 10 (B->H)

A->B->C = 5 + 15

A->B->D = 5 + 10

The list in order will now look like;

1. A->H with 10 meters
2. A->P with 10 meters
3. A-> O with 15 meters
4. A->B->H with 15 meters
5. A->B->D with 15 meters
6. A->B->C with 20 meters

And the “visited nodes” list will look like:

-A

-B

->The program will continue until all the “paths” are found and classified from the lowest to the highest cost thus distance. The “visited nodes” list will prevent it from checking multiple times the same path thus doing evitable and useless operations.

Here is a visual representation of how Dijkstra algorithm process in a graph ;

The algorithm may still be blurry for you so you might want to watch this 8 min animation : https://www.youtube.com/watch?v=bZkzH5x0SKU

You also have a french excellent video by the Math teacher Yvan Monka : https://www.youtube.com/watch?v=rHylCtXtdNs

So now we have successfully modeled our situation and chosen an algorithm. Let's program it !

*slurps coffee and cracks his hands*

Here it is : https://github.com/Aur3m/Dijkstra-demo-charlies-oib/blob/main/dijkstra.py

Technical notes : I did the program in Python using the Heapq module to automatically sort in an optimized way. The graph data was directly written within a python dictionary because it is much more convenient and quick to access.

When I try it on my pc here are the final results ;

Here on the second line we can see the output of the program which are the details of a shortest path found and its total distance which is a->h->k->m->n->z and is 55 meters. (If you’re skeptical I invite you to go back to the graph to find out that this is indeed the shortest path).

But one thing that astonishes me, it’s the execution time before obtaining this result at line 3 ; it indeed took 0.000054 seconds or 0.054 ms which is less than 1 ms ! Now I can clearly understand why all GPS Services use this type of algorithm and how it can easily and quickly calculate long itineraries.

Why were my holidays “eventful” ? & Conclusion :

Finally !!! This is the part where I assume you are now all experts and I use complex vocabulary without restrictions ! I’m kidding but seriously, if you’re interested don’t hesitate to register for next year's prologin's edition. It was a very fun, challenging and enriching experience as I didn’t even know what a graph really was before February holidays.

This shows that even though you have not advanced knowledge you can still manage to start the competition and if you’re qualified for the regionals start to seriously practice which is exactly what I did during last holidays.

Although you’re not left alone ; when you are qualified for the regionals for prologin, you are given a list of scripts and algorithmics notions you are expected to know if you want to resolve the problems which will be proposed. In the list there is of course Dijkstra shortest path algorithm but a lot more like Prim minimum spanning tree or Ford Fulkerson max-flow algorithms if you want to look up at them on the internet. During the tests though, you will never be able to put directly the scripts you have learnt but you'd rather get inspiration from them in order to compose efficient solutions (because each problem needs to be resolved within a certain execution time !).

For example 2 years ago, a modified version of Dijkstra could have worked to resolve a problem where we needed to calculate the most optimized path for the least fuel costs possible [Page 9-10] : https://prologin.org/static/archives/2020/questionnaire/correction.pdf 

(though another solution presented just before using dynamic programming was more optimal)

To finally conclude this article because it is getting too long, I would say that if you like coding or would like to code and you are under 20, this is definitively an opportunity you don’t want to miss even though at the beginning it might frighten you. I was completely lost when I first saw the algorithms prologin recommended. But practice makes perfect and the internet is really crammed with helpful resources. If you want me to share some of them with you just leave a comment👍

(and yes the final INDEED consists in a 36h of "non-stop" programming in EPITA Paris but of course you’re still allowed to sleep in a dormitory within the campus)