Thursday, May 29, 2014

The Algorithms that Dominate our World Are More Basic Than You Might Think

From Medium:

The real 10 algorithms that dominate our world
The other day, while I was navigating Reddit 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 words is possible to say that an algorithm is a sequence of steps which allow to solve a certain task ( Yes, no just computers use algorithms also humans use them). Now, an algorithm should have three important characteristics to be considered valid:
  1. It should be finite: If your algorithm never ends trying to solve the problem it was designed to solve then it is useless
  2. It should have well defined instructions: It has to be precisely defined each step of the algorithm; the instructions should be unambiguously specified for each case.
  3. 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 is important to say that algorithms are used in Computing Sciences but they are a mathematical entity, in fact the first mathematical algorithms that we have registry are 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 a put a little list of which are this algorithms 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 in what you need and that’s why I put the three more used sort algorithms in the same place, maybe you have a preference in one of them but all of them are equal 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 approach divide and conquer to solve a problem that once was a O(n^2). It was invented by the mathematician Jhon 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 too. 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 used like bubble sort, in fact 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 that transform signals from their time domain into their frequency domain and viceversa. In fact, you are seen this post thanks to these algorithms.
The internet, your WiFi, smartphone, phone, computer, router, satellites, almost everything that has a computer inside use this algorithm to work, in one way or another. You can’t study a degree in electronics, computing or telecommunications without studying these important algorithms.

3. Dijkstra’s algorithm
Is not crazy to say that the internet wouldn't work as efficient 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.

Even when today we have better solutions for the problem of finding the shortest path, Dijkstra’s algorithm is still used in systems that require stability....MORE