What Is an Algorithm?

Sunday, 7 September 2014

If you search the web the definition of algorithm, the more frequent answer is “An algorithm is a finite sequence of instructions defined and unambiguous, each of which can be performed in a finite period of time and a finite amount of effort.”. But this is just a basic idea. If somehow you’ve never heard about that word, be assured you execute it on a daily basis.

Have you ever cooked?! If yes, you followed the recipe steps to have the desired food. If the sequence of steps is not followed as it is written in recipe, the end result cannot be as the expected one. When you are going to hang out with friends… Do you put on your shoes before the socks and then wear the pants? Such steps aren’t really ideal, right?! This algorithm can be performed in three different ways and it will end up producing the same outcome. But these examples are simple, for there are much more complex algorithms, and others algorithms only exist in theory. Huh?! How so?! Just keep reading…

Perhaps Algorithm is the most used term in Computer Science. But it doesn’t represent a specific computer program. It may have its implementation and execution on a computer, a mechanical machine, another automata, and even, of course, by you. Different algorithms can accomplish the same task using a different set of instructions which may result in longer or shorter of time, bigger or smaller space, or heavier or lighter effort. These attributes are related to the computational complexity that was applied to the algorithm and that depends directly on the data structure that was built into it. Going back to the previous examples, it might seem obvious that if you put your socks and shoes and then wear the pants will take longer and be more work than you wear the pants first. Two different algorithms, but they will produce the same result.

There are several ways to represent an algorithm more formally, some of them are a flowchart, coding and automata. Even more specific types of algorithm, such as neural, natural, sort, search, encryption, meta-heuristics, quantum, and many others.

About theoretical algorithms, an example that can be given is the Traveling Salesman Problem (TSP), that is an optimization problem of finding the route of least effort in which the Salesman visit exactly once all the cities and then return to your original city, but precisely it’s about to find the lowest cost across all nodes of a weighted graph. The computational effort required to solve this problem grows exponentially in scale in relation to the given input (number of cities). In Analysis of Algorithms, it belongs to a class called NP-hard or NP-complex. Thus, since it is resourcely impossible to determine optimal solution of this class of problems, methods of resolution that go through heuristics that, in the mathematical point of view, do not ensure obtaining an optimal solution, but try to approximate as much as possible the optimal resolution.

This was a brief idea about what an algorithm is, usually mispoken as algarithm (there is no such word) and algarism.

Seven Sorting Algorithms in a Few Lines »