Algorithms that dominate our world !

Now if you have studied algorithms the first thing that could come to your mind while reading the article is “Does the author know 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 solving 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:

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: Each step of the algorithm has to be precisely defined; 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, 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 let's take computing algorithms as our definition of an 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

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-based sorting algorithm that uses the divide-and-conquer approach to solving a problem that once was an O(n^2). It was invented by the mathematician John von Neumann in 1945.

A 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 a 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

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 cybersecurity. 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 on 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 hasn’t been completely solved, I think we need more work in this direction).

5. 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 the 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 an eigenvalue problem. These eigenvalues can give you a really good approach to 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 though 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

Have you ever used an airplane, an automobile, a satellite service or a cell phone 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 exist.

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 zipping 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 could you 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.

Algorithms ruling the world !!

Algorithms have revolutionized our world as we know it. 

Today, a lot of things come to us a lot more easily than before. We have moved forward from the age of waiting to hear our favorite song on the FM radio and recording it on a cassette. Now, we visit YouTube to play your favorite song. It miraculously recommends all your favorite songs in the auto playlist. 

When you visit IMDB’s website, it suggests the most relevant movies every time. When you Google something, you see the most relevant information on the first page. Have you ever wondered how each website knows exactly what to show you?

Algorithms.

We have advanced so much that we can create a painting that one cannot distinguish from the works of an artist who died in 1669!

We are talking about the new 3D-printed Rembrandt painting. Developers created an algorithm to collect data from portraits painted by Rembrandt. This data was then used to create a new 3D-printed painting, which took over 500 hours of rendering.

What is an algorithm?

“A process or set of rules followed in calculations or other problem-solving operations, especially by a computer”. At the simplest level, it is a procedure for accomplishing a task or solving the problem. 

How algorithms shape our world every day

Algorithms are everywhere—sports, computer gaming, finance etc. Let us take a look at a few examples.

Healthcare: Algorithms help in areas where healthcare had no effective treatment. From matching appropriate organs to mining data for matching symptoms. They complement some of the most proficient doctors across the globe.

In 2013, 4500 former footballers filed lawsuits against the NFL for concussion-related injuries. This issue came into the limelight when Hall of Famer, nine-time Pro Bowler, Mike Webster and a few other players were diagnosed with Chronic Traumatic Encephalopathy (CTE). The effects of repeated blows to the head cause CTE. 

1.6 to 3.8 million sports-related concussions occur annually in the United States. To this day, there are no effective tests/scans to detect this disorder. Sanford Health studied common symptoms of the disorder and developed a concussion-evaluation algorithm, which detects the signs and symptoms of CTE. Now, because of timely treatment and precautions, the effects of concussions are prevented in more players. Until an effective test or scan is developed, algorithms are the answer to detecting CTE in time.

Sports: The sports industry today is the result of what has moved from intuition to statistics. It is a big game of algorithms from the Duckworth-Lewis method in cricket to the ranking players by using the Elo rating in the game of chess.

Algorithms also dominate the world of sports betting. So when you see weird numbers like 12/25 for ManU and 17/25 for Arsenal, you can rest assured that they are correct. The complex mathematical concept of the Poisson distribution equation is the foundation to the sports betting. This concept is used to generate numbers in sports betting.

Let’s take the example of Elihu Feustel, who makes almost a million dollars a day by betting on tennis. You would think that he would recognize Serena Williams if he passed by her on the street. However, this isn’t the case, he neither recognizes any of the famous tennis players nor does he know their playing styles etc. So, just how does he know who to bet on? He relies on a big data model that the live betting market uses. This algorithm collects data from existing (almost 2,60,000) matches. This data is then manipulated to allow users to determine which player/match they should bet on.

It seems like it’s all out of this world, right?

Gaming: It's amazing how videos and computer games have evolved over the last 2 decades. We started with DOS games, Super Mario, Pac-Man, and went on to highly-advanced games like Need for Speed, Counter-Strike, and DotA.

The games are now getting more realistic, with life-like surroundings, smarter and scarier anti-heroes. There is an increased advancement in Augmented Reality (AR) and Virtual Reality (VR) technologies. We are now developing techniques to bring in games that require player involvement at an epidemic rate. This has led to the development of algorithms that are highly complex in nature to create complex games.

There is no doubt that irrespective of the field that you choose, algorithms have a strong influence on our lives and they are changing our world.

Soon there is a possibility that algorithms will take over most of the tasks done by human beings. This could lead to the creation of mundane jobs, which algorithms cannot do, such as stocking bottles, collecting blood samples, and other work that requires physical effort.

Fibonacci in Nature

The Fibonacci numbers are Nature's numbering system. They appear everywhere in Nature, from the leaf arrangement in plants to the pattern of the florets of a flower, the bracts of a pinecone, or the scales of a pineapple. The Fibonacci numbers are therefore applicable to the growth of every living thing, including a single cell, a grain of wheat, a hive of bees, and even all of mankind.

Plants do not know about this sequence - they just grow in the most efficient ways. Many plants show the Fibonacci numbers in the arrangement of the leaves around the stem. Some pine cones and fir cones also show the numbers, as do daisies and sunflowers. Sunflowers can contain the number 89, or even 144. Many other plants, such as succulents, also show the numbers. Some coniferous trees show these numbers in the bumps on their trunks. And palm trees show the numbers in the rings on their trunks.

Why do these arrangements occur? In the case of leaf arrangement or phyllotaxis, some of the cases may be related to maximizing the space for each leaf, or the average amount of light falling on each one. Even a tiny advantage would come to dominate, over many generations. In the case of close-packed leaves in cabbages and succulents, the correct arrangement may be crucial for availability of space.

In the seeming randomness of the natural world, we can find many instances of mathematical order involving the Fibonacci numbers themselves and the closely related "Golden" elements.

Fibonacci in Plants

Fibonacci in Animals

Fibonacci in Animals

The shell of the chambered Nautilus has Golden proportions. It is a logarithmic spiral.

The eyes, fins and tail of the dolphin fall at Golden sections along the body.

A starfish has 5 arms.  (5 is the 5th Fibonacci number)

If a regular pentagon is drawn and diagonals are added, a five-sided star or pentagram is formed. Where the sides of the pentagon are one unit in length, the ratio between the diagonals and the sides is Phi, or the Golden Ratio. This five-point symmetry with Golden proportions is found in starfish.

Humans exhibit Fibonacci characteristics, too. The Golden Ratio is seen in the proportions in the sections of a finger.

It is also worthwhile to mention that we have 8 fingers in total, 5 digits on each hand, 3 bones in each finger, 2 bones in 1 thumb, and 1 thumb on each hand.
The ratio between the forearm and the hand is the Golden Ratio!

The cochlea of the inner ear forms a Golden Spiral.

Fibonacci in Plants

Phyllotaxis is the study of the ordered position of leaves on a stem. The leaves on this plant are staggered in a spiral pattern to permit optimum exposure to sunlight. If we apply the Golden Ratio to a circle we can see how it is that this plant exhibits Fibonacci qualities. See picture for more detailed illustration of leaf arrangements.

By dividing a circle into Golden proportions, where the ratio of the arc length is equal to the Golden Ratio, we find the angle of the arcs to be 137.5 degrees. In fact, this is the angle at which adjacent leaves are positioned around the stem. This phenomenon is observed in many types of plants.

In the case of tapered pinecones or pineapples, we see a double set of spirals – one going in a clockwise direction and one in the opposite direction. When these spirals are counted, the two sets are found to be adjacent Fibonacci numbers. 

Similarly, sunflowers have a Golden Spiral seed arrangement. This provides a biological advantage because it maximizes the number of seeds that can be packed into a seed head.

Inside the fruit of many plants, we can observe the presence of Fibonacci order.

                                                           The banana has 3 sections     The apple has 5 sections

As well, many flowers have a Fibonacci number of petals. Some, like this rose, also have Fibonacci, or Golden Spiral, petal arrangements.

Branching plants also exhibit Fibonacci numbers. Again, this design provides the best physical accommodation for the number of branches, while maximizing sun exposure.

Fibonacci Petals

3 petals                  lily, iris

5 petals                  buttercup, wild rose, larkspur, columbine

8 petals                 delphiniums

13 petals                ragwort, corn marigold, cineraria

21 petals                aster, black-eyed Susan, chicory

34 petals                plantain, pyrethrum

55, 89 petals          Michaelmas daisies, the Asteraceae family

The occurrence of Fibonacci Numbers in Nature is interesting but the ratio of consecutive Fibonacci Numbers is important.

The Golden Mean (Φ)

The Golden Mean (or Golden Section), represented by the Greek letter phi, is one of those mysterious natural numbers, like e or pi, that seem to arise out of the basic structure of our cosmos. Unlike those abstract numbers, however, phi appears clearly and regularly in the realm of things that grow and unfold in steps, and that includes living things.

The decimal representation of phi is 1.6180339887499... .

How to Construct a Golden Section?

A golden section may be constructed in several ways. The following method of construction is one of them:

Draw a line segment AB of length a on the straight line PQ.

Now construct a perpendicular BD of length a at B. Bisect AB at E with E as the centre and ED as the radius, describing an arc that intersects PQ at C.

Then by Pythagoras theorem, the radius

We have,

Here, AC is divided in the golden ratio by the point B.

The Golden Spiral

When a Golden Rectangle is progressively subdivided into smaller and smaller Golden Rectangles the pattern below is obtained. From this, a spiral can be drawn which grows logarithmically, where the radius of the spiral, at any given point, is the length of the corresponding square to a Golden Rectangle. This is called the Golden Spiral.

The spiral converges at the intersection of the two blue lines (P), and the ratio of the lengths of these two lines BP: PD is Φ, the Golden Ratio.

The Golden Ratio

Geometry has two great treasures: one is the theorem of Pythagoras; the other, the division of a line into extreme and mean ratio. The first we may compare to a measure of Gold; the second we may name a Precious jewel. – Kepler (1571- 1630)

In everyday life, we use the word “proportion” either for the comparative relation between parts of things with respect to size or quantity or when we want to describe a harmonious relationship between different parts. In mathematics, the term “proportion” is used to describe an equality of the type: nine is to three as six is to two. The Golden Ratio provides us with an intriguing mingling, it is claimed to have pleasingly harmonious qualities.

The first clear definition of what has later become known as the Golden Ratio was given around 300 B.C by the founder of geometry as a formalized deductive system , Euclid of Alexandria.

  

In Euclid’s words:

A straight line is said to have been cut in extreme and mean ratio when, as the whole line is to the greater segment, so is the greater to the lesser.

If the ratio of the length AC to that of CB is the same as the ratio of AB to AC, then the line has been cut in extreme and mean ratio, or in a Golden Ratio.

The Golden Ratio is thus the ratio of the larger sub-segment to the smaller. If the whole segment has length 1 and the larger sub-segment has length x (Figure 2), then

PageRank - Google's Algorithm ( The heart of google )

What is it?

PageRank is an algorithm used primarily for rating the popularity of web pages. Although one may initially think 'Page' refers to the web page, it actually refers to the inventor, Larry Page (a founder of Google). This is why you'll find the capital 'P' wherever you find a reference to the algorithm.

The basic assumption is that the more inbound links a web page has across the web, the more valid the content the page contains. It's a crowd-sourcing algorithm of sorts; it relies on everybody online to create a network of links to different web pages and classifies the validity of each page based on its overall popularity.

Applications

The most obvious application of PageRank is the Google search engine. In fact, much of the company's initial success may be attributed to the effectiveness of PageRank in organizing search results on Google.

It is important to note, however, that it is not only web pages which may use PageRank. Any data which can be modeled as a directional graph can be analyzed with PageRank.

The Math

Consider a directional graph, where web pages are modeled as nodes, and the links are modeled as vertices. Each vertex represents a link from one page to another.

While it may be tempting to simply count the total number of links pointing to each web page to discover which page is the most popular, PageRank is a bit more sophisticated.

We begin by assigning each node a score between zero and one. This score represents a probability distribution. If you are unfamiliar with probability distributions, don't worry. This example will make sense regardless.

The initial score is:

PR(N) = 1/n

This reads as "The PageRank of each node is one divided by the total number of nodes in the network." Each node starts with the same initial score.

Let's use an example network with five nodes: A, B, C, D, and E. In this case, each node has an initial score of 0.2. Now imagine a link:

A -> C

This would transfer all of A's scores to C, leaving A with 0 and C with 0.4.

Imagine A with two outbound links:

A -> C
A -> D

In this case, A would still have 0, but C and D would split the 0.2 from A. This leaves D with 0.3 and C with 0.3.

Be aware that this is an example of a simple Page Rank algorithm. More advanced implementations will use tools such as a damping factor.

Input Description

This is a simple implementation of the PageRank algorithm. It accepts an input in the form of an int[][] or a String which can define the d value and the number of loops. The default d value is 0.85, and the default number of loops is 20

page 0 links to pages 1,2,3
Page 1 links to page 0
Page 2 links to page 0
Page 3 links to pages 0,4,5,6,7
page 4 has no links
page 5 has no links
page 6 has no links
page 7 has no links

Sample Input

[[1,2,3],[0],[0],[0,4,5,6,7],[],[],[],[]]

Sample Output

[0.9142543787391981,0.4089334112608257,0.4089334112608257,0.4089334112608257,0.21947767079447258,0.21947767079447258,0.21947767079447258,0.21947767079447258]