A quick study of algorithmic key concepts: graphs, heaps…

As their name implies, algorithmics deal with building, studying and optimizing algorithms (by reducing execution time or used memory for example). While the field comprises several grand directions such as algorithm design, complexity theory and analysis, all of these are closely related to each other which makes it kind of hard to treat ‘the science of algorithms’ as a whole.

During my engineering studies, I was explained some basic algorithmic concepts like graphs and abstract data types. Then, I had to reuse those in a programming project to get a more comprehensive understanding of the notions. Seven topics were proposed and I decided to tackle a few, especially to see how they could be interlinked, how one could help in solving another and so on.

[projectinfo languages=”c” team=”1″ duration=”2 weeks”]

The complete code of the project can be downloaded here and the dossier (in French) here.

A ‘hand-on’ approach of graphs, heaps and trees

The goal of this project was to show us practical applications of the theories we had learnt before and to make us implement these structures ourselves. To me, it was really great to be able to model things like a subway map or chemical compounds interaction and apply algorithmic abstract notions on them.

For example, the problem of Moravia’s electrical network that inspired Boruvka his famous minimal spanning tree search algorithm gives you a pragmatic case study: instead of wondering about ‘how to get the shortest path that goes through all the nodes of your graph’, you’d rather ask yourself ‘how to design the cheapest network that has the shortest wiring but still brings light to all the houses in the city’. This way, when you solve your abstract model and you get back to reality, you actually understand what it means.

Dive into more complex algorithmic paradigms and data types

It was also an opportunity to discover more advanced types of algorithms and data structures than the ones shown in our course. In particular, I worked on the Bloom filter and its applications in text analysis and orthographic correction; I did a quick study of binomial heaps that can be used in path-search algorithms like Dijkstra’s; and I took a look at the advantages of dynamic programming to optimize problem solving.

It was fascinating to try and decide what data type and algorithm design fit your problem best and I feel connecting the topics was a good way to see the strengths and weaknesses of the different objects I handled.

The next step?

Peeking into graphs theory is, I believe, essential for programmers today, given that so many programs rely on them. It can lead you to graph databases like Neo4j, mathematical optimization and team management…

All in all, graphs are a modeling tool for almost every domain you can think of: physics, chemistry, economy, geography, social interactions and so much more! Many real-life systems can be turned into and analyzed with graphs.

This project triggered a real interest in mathematical modelization and, since then, I have had plenty of amazing courses that have confirmed the basic concepts I barely glimpsed at with this dossier are everywhere around us.

  1. B. H. Bloom, “Some techniques and trade-offs affecting large data base retrieval times,” ACM ’69 Proceedings of the 1969 24th national conference, pp. 83–95, August 1969.
  2. I. Wikimedia Foundation, “Bloom filter.” (https://en.wikipedia.org/wiki/Bloom_filter), May 2018. [Online; last access 13-April-2017].
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “BINOMIAL HEAPS,” in Introduction to Algorithms, ch. 20, Al. Cormen, 1990.
  4. I. Wikimedia Foundation, “Dynamic programming.” (https://en.wikipedia.org/wiki/Dynamic_programming), May 2018. [Online; last access 24-April-2017].
  5. I. Wikimedia Foundation, “Boruvka’s Algorithm.” (https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm), Apr. 2018. [Online; last access 28-May-2018].
  6. I. Wikimedia Foundation, “Dijkstra’s Algorithm.” (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), Apr. 2018. [Online; last access 28-May-2018].
  7. Shivam, “Binomial Heap.” (http://www.geeksforgeeks.org/binomial-heap-2/) [Online; last access 17-April-2017].
  8. I. Wikimedia Foundation, “Graph database.” (https://en.wikipedia.org/wiki/Graph_database), May 2018. [Online; last access 28-May-2018].
  9. Neo4j’s website: https://neo4j.com/

Leave a Reply

Your email address will not be published.