The real 10 algorithms that dominate our world
Maybe a little bit more than 10
I post this article here based on a post on Medium by Marcos Otero. Unfortunately he decided to shut down his post so I’m putting it here.
The other day, while I was navigating on the web I found an interesting post that was called The 10 Algorithms That Dominate Our World by the author George Dvorsky which was trying to explain the importance that algorithms have in our world today and which ones are the most important for our civilization.
Now if you have studied algorithms the first thing that could come to your mind while reading the article is “Does the author knows what an algorithm is?” or maybe “Facebook news feed is an algorithm?” because if Facebook news feed is an algorithm then you could eventually classify almost everything as an algorithm. So I’m going to try to explain in this post what an algorithm is and which are the real 10 (or maybe more ) algorithms that rule our world.
What is an algorithm?
Informally, an algorithm is any well-defined computational procedure that takes
some value, or set of values, as input and produces some value, or set of values, as
output. An algorithm is thus a sequence of computational steps that transform the
input into the output. Source: Thomas H. Cormen, Chales E. Leiserson (2009), Introduction to Algorithms 3rd edition.
In simple terms, it is possible to say that an algorithm is a sequence of steps which allow to solve a certain task ( Yes, not just computers use algorithms, humans also use them). Now, an algorithm should have three important characteristics to be considered valid:
It should be finite: If your algorithm never ends trying to solve the problem it was designed to solve then it is useless
It should have well defined instructions: Each step of the algorithm has to be precisely defined; the instructions should be unambiguously specified for each case.
It should be effective: The algorithm should solve the problem it was designed to solve. And it should be possible to demonstrate that the algorithm converges with just a paper and pencil.
Also it is important to point out that algorithms are not just used in Computing Sciences but are a mathematical entity. In fact the first recorded mathematical algorithms that we have date from 1600 BC — Babylonians develop earliest known algorithms for factorization and finding square roots. So here we have the first problem with the post mentioned before, it treats algorithms as computing entities, but if you take the formal meaning of the word the real top 10 algorithms that rule the world can be found in a book of arithmetic (addition, subtraction, product, etc).
But lets take computing algorithms as our definition of algorithm in this post, so the question remains: Which are the 10 algorithms that rule the world?. Here I’ve put together a little list, in no particular order.
1. Merge Sort, Quick Sort and Heap Sort
http://rkandhal.com/wp-content/uploads/2013/10/sort-comparison.png
What is the best algorithm to sort elements? It depends on what you need, and that’s why I put the three more frequently used sort algorithms in the same place; maybe you have a preference for one, but all of them are equally important.
The Merge Sort algorithm is by far one of the most important algorithms that we have today. It is a comparison-base sorting algorithm that uses the divide-and-conquer approach to solve a problem that once was a O(n^2). It was invented by the mathematician John von Neumann in 1945.
Quick Sort is a different approach to the sorting problem, it can use in-place partition algorithms and is a divide and conquer algorithm as well. The problem with this algorithm is that is not a stable sort but is really efficient for sorting RAM-based arrays.
Finally, Heap Sort algorithm uses a priority queue that reduces the search time in the data. This algorithm is also an in-place algorithm and is not stable sort.
These algorithms are a big improvement over other approaches previously used like bubble sort, in fact, it is thanks to them that today we have Data mining, artificial intelligence, link analysis and most of the computing tools in the world including the web.
2. Fourier Transform and Fast Fourier Transform
Our entire digital world uses these simple but really powerful algorithms, which transform signals from their time domain into their frequency domain and vice versa. In fact, you are seeing this post thanks to these algorithms.
The internet, your WiFi, smartphone, phone, computer, router, satellites, almost everything that has a computer inside uses these algorithms in one way or another to function. You can’t get a degree in electronics, computing or telecommunications without studying these important algorithms.
3. Dijkstra’s algorithm
https://www.cs.indiana.edu/~achauhan/Teaching/B403/LectureNotes/10-graphalgo.html
It is not crazy to say that the internet wouldn’t work as efficiently as it does if it wasn’t because of this algorithm. This graph search algorithm is used in different applications where the problem can be modeled as a graph and you have to find the shortest path between two nodes.
Today, even when we have better solutions to the problem of finding the shortest path, Dijkstra’s algorithm is still used in systems that require stability.
4. RSA algorithm
The internet wouldn’t be as important as it is today if it wasn’t for cryptography and cyber security. You can think “Sure, security in the era of NSA and other intelligence agencies” or “You have to be really naive to think you are safe in the Internet”; but, people need to feel that they are secure in order to spend their money. After all, you wouldn’t input your credit card number on a web service if you know it is not secure.
And from the field of cryptography there is an algorithm that remains one of the most important in the world: the RSA algorithm. Developed by the founders of the company RSA, this algorithm made cryptography available to everybody in the world and helped to shape how cryptography works today. The RSA algorithm is a solution to a simple but complex problem: how to share public keys between independent platforms and final users, in order to allow cryptography (I would argue that it has been completely solved, I think we need more work in this direction) .
- Secure Hash Algorithm
This isn’t exactly an algorithm but a family of cryptographic hash functions developed by the NIST in the USA. But this family of algorithms is fundamental for the functioning of the World. From your app store, your email, your antivirus, to your browser, etc , all of them use these algorithms (in reality the hash that results from them) to determine if you have downloaded what you wanted or if you have been the victim of a man in the middle attack or maybe a phishing attack.
6. Integer factorization
This is a mathematical algorithm that is heavily used in computing field. Without this algorithm, cryptography would be much more unsafe. The algorithm is a series of steps used to get the prime factorization of a composite number into smaller non-trivial divisors. This is considered an FNP problem, which is an extension of the class NP making the problem really hard to solve.
Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.
The birth of quantum computing is making it easier to solve this problem, opening a completely new field that uses properties of the quantum world to make systems safe.
7. Link Analysis
In the era of internet, the analysis of relationships between different entities is crucial. From search engines and social networks to marketing analysis tools, everybody is trying to find the real structure of the Internet through time.
Link analysis is arguably one of the algorithms with the most myths and confusion in the general public. The problem is that there are different ways to make link analysis and there are also characteristics that make each algorithm a little different (which allows to patent the algorithms) but in their bases they are similar.
The idea behind link analysis is simple, you can represent a graph in a Matrix form making it a eigenvalue problem. This eigenvalues can give you a really good approach of the structure of the graph and the relative importance of each node. The algorithm was developed in 1976 by Gabriel Pinski and Francis Narin.
Who uses this algorithm? Google in its Page Rank, Facebook when it shows you your news feed (this is the reason why Facebook news feed is not an algorithm but the result of one), Google+ and Facebook friend suggestion, LinkedIn suggestions for jobs and contacts, Netflix and Hulu for movies, YouTube for videos, etc. Each one has a different objective and different parameters, but the math behind each remains the same.
Finally, I’d like to say that even thought it seems like Google was the first company to work with this type of algorithms, in 1996 (two years before Google) a little search engine called “RankDex” , founded by Robin Li, was already using this idea for page ranking. Finally Massimo Marchiori, the founder of “HyperSearch”, used an algorithm of page rank based on the relations between single pages. (The two founders are mentioned in the patents of Google).
8. Proportional Integral Derivative Algorithm
https://en.wikipedia.org/wiki/File:PID_en_updated_feedback.svg
Have you ever used an airplane, an automobile, a satellite service or a cellphone network? Have you ever been in a factory or seen a robot? If so, then you have seen this algorithm in action.
Basically, this algorithm uses a control loop feedback mechanism to minimize the error between the desired output signal and the real output signal. It is used wherever you need signal processing or you need an electronic system controlling a mechanical, hydraulic or thermal system using automation.
You could say that without this algorithm our modern civilization wouldn’t exists.
9. Data compression algorithms
It is difficult to decide which is the most important compression algorithm because, depending on the application, the algorithm used can vary from zip to mp3 and from JPEG to MPEG-2. But there is something that everybody knows that these algorithms are really important in almost all the structures.
Where can you could find them, besides the obvious zipped document? This web page used data compression to be downloaded into your computer, in video games, videos, music, data storage, cloud computing, databases, etc. You could say that everything uses data compression algorithms; they help make systems cheaper and more efficient.
10. Random Number Generation
Today we don’t have a “true” random number generator, but we have some pseudo random number generators that are sufficient. These are used in a large number of applications, from interlink connection, cryptography, secure hash algorithm, video games, artificial intelligence, optimization, to initial conditions for problems, finances, etc.
Finally I just want to add that this list should be taken as an opinion, not a comprehensive list, because there are some algorithms in fields like Machine Learning, Matrix multiplication, categorization, etc, which are important in our world and are not mentioned here.