Hi. In this part on algorithmics, we've seen tasks, the division of an algorithm into small simple tasks. Then, we've seen variables and the complete list of elementary instructions allowing us to write every algorithm. We'll now take a step back from algorithmics as a science to show you what else we can do, more generally.
Particularly concerning data structures, there are many much more complex structures existing in computer science, I'll give you a non-exhaustive list. There are the lists Brice talked about in the data organization sequence doubly linked lists, more complex, where there are links from one to the next, but also to the previous the stacks and queues that are especially used to store tasks to carry out hash tables to represent sets trees and heaps that are more complex structures, but with many underlying structures the graphs I'll talk about a bit later and the databases on which you also have a sequence on.
I'll talk about graphs. The drawing on this slide is a graph. They are boxes called nodes and edges, so arrows from one node to another. They're used to represent many things. For instance, a network, Internet network, electrical network, or water network. They can represent dependencies. I need to have to go through C to do B or relationships, A and B know each other. There are different types of graphs. This graph has arrows, but there are graphs without arrows, called undirected graphs. How do we represent that with data structures? There are several options. One is the adjacency graph, there's a Boolean that indicates if two nodes are linked. When given two nodes, for instance, A and C, it'll answer true because A is linked to C. Another way to represent a graph is with a neighbour list. Graph A has two neighbours, B and C. Graph C has no neighbour.
Now, I'll show you a graph that is a bit more complex and represents this part of the course. The "computer science and its foundations" course parts are represented by this graph. Each node is a sequence. Then, the arrows represent the dependencies. For instance, I1 and I2, are sequences of the binary coding of the information part, you need to have watched I1, so I1.1 to watch sequence I1.2. Similarly, all I1 represents the binary coding of information courses, I2 are the algorithmics courses, where you are now. I3 is programming, and I4 is computer and network architecture. The dependency graph is here. Say you want to watch a given sequence, how will you know which sequences you need to watch before?
I can give you an algorithm I'll unfold right after. As input, you have a dependency graph that is exactly the drawing on the previous slide where neighbours are stored as a list. I have a start node n which is the sequence I'd really like to watch, and the input is the list of the dependencies of n, so the sequences I need to watch to watch the sequence n. You have several variables. The first variable is "res" which will be the result, initialized as empty. "to_process" is a temporary variable, it's all I have to process. I initialize as empty, then I add n in it since n is the initialization, what do I have to process?
I need to process n for now. Then, I look at the "to_process" variable that can be represented with several different data structures, by the way. As long as it's not empty, I take a value out of this list or data structure. I extract it completely. I retrieve x and "to_process" is the previous "to_process" without this x variable. I add x in the result
What does it look like, with an example? Say I want to watch the sequence I4.2, what do I have to watch before? I have colours to represent the different variables. "to_process" will be in red, the result in green, and x, the one I'm working on at a given moment, will be in blue. At the beginning, I start from I4.2, so I need to process I4.2. So I4.2 is indeed the x I'm working on. Then, I examine all its children, and I put them in "to_process".
Now, I4.2, which was the x, has gone into the results since I depend on it. I have a list of things to process, so the three red nodes. Then I take a red node, anyone, the data structure will give me one, it doesn't matter. Say I take I3.2. It's the new x. it's the one I'm looking at.I take all its children. It only has one, I3.1, which is added to "to_process". I've I3.2 that I've added to the results. I'll iterate like this. Each time, I'll add the children in red and each time, I'll take a red one and add all its children. This is what we get. To watch I4.2, I have to watch all these sequences.
So you've seen an example of the path in a graph. Of course, algorithmics is not just about graphs. There are many other data structures and many other algorithms. Here's a non-exhaustive list of books and references you can have a look at. There are three books in English, by Sedgewick and Knuth, and then several references in French, one in OCaml, one in Python, and one in Java.