# Which are the significant algorithms for humankind in past decades? [closed]

Which world most important algorithms have contributed most to humankind in past decades?

I thought this is a good general knowledge for a developer to know about.

Update:
If possible, please keep the answer to a specific programming algorithm.
I would like to get a list of the most important ones, only one algorithm per answer.
Please consider to state why the algorithm is significant and important...

• It's being closed because (so far) four people consider it "not a real question", probably because we don't have any real idea what, in isolation, an important programming algorithm is. Commented Nov 19, 2010 at 21:40
• It might be off-topic, but its a real question. Commented Nov 19, 2010 at 22:32
• +1 Good question. I suggest re-asking this on cstheory.stackexchange.com Commented Nov 21, 2010 at 7:46
• Why do you answer your own questions? Several times?
– user1249
Commented Nov 26, 2010 at 21:04
• No wrong answers + unlimited number of answers + an unambiguous comment asking for "one per answer" + author posts several of his own answers = textbook case of a non-constructive question. I know it's old, but let's please close this. Commented May 27, 2011 at 21:17

## 28 Answers

Public/private key encryption is pretty darn important. Internet commerce would be nowhere as ubiquitous without it.

• +1 and to add to your answer, RSA. Commented Nov 19, 2010 at 20:45
• There's a whole group of algorithms and best-practices involved in turning cryptographic codes (like RSA) into practical solutions. Commented May 28, 2011 at 11:26

Dijkstra's algorithm

The algorithm exist in every router in the world, for identifying the best route between two nodes in a network.

• Are you sure? Most routers either know that the IP-number belongs to it and forwards it to the machine on the local network, or know a router who know better - the default router - in which case the packet goes to that router. Big routers may know that for IP-address range X1-Y1 the packet should go to router R1, for range X2-Y2 the packet should go to router R2, etc. There is no Dijkstras algorithm involved in this.
– user1249
Commented Nov 19, 2010 at 23:41
• @Thorbjørn Ravn Andersen: But for the router to know that information, someone at some point would have had to use Dijkstra's algorithm. Yes, it's not used for actually routing each individual packet, but it is used in determining routing tables on big networks. +1. Commented Nov 20, 2010 at 1:06
• @Billy, where exactly would you expect that the Dijkstra algorithm is actually used and by whom?
– user1249
Commented Nov 20, 2010 at 7:19
• @Thorbjørn Ravn Andersen: To my understanding, it plays a role in OSPF, which is the foundation of choosing the correct routes for small networks. Connections between larger networks use BGP, which is more policy based. I'm not sure if BGP uses Dijkstra's algorithm or not. Commented Nov 20, 2010 at 15:59
• @Billy, but my objection was to "exists in EVERY router in the world". That is - in my opinion - plainly wrong.
– user1249
Commented Nov 26, 2010 at 21:05

The FFT is an extremely important and widely-used method of extracting useful information from sampled signals.

A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse.

• I had a boss once who, decades earlier, had written a series of FFT functions for the PDP-11. He sold a deck of punchcards with those functions with an ad in the back of Popular Science, and made pretty serious bank. Evidently he had people using his code for everything from signal processing to stock market prediction. Commented Nov 24, 2010 at 13:10

PageRank

PageRank is a link analysis algorithm, named after Larry Page, used by the Google Internet search engine that assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set.

• haha, our answers were just 2 seconds apart,sorry :) Commented Nov 19, 2010 at 20:48
• no problem at all! :) Commented Nov 19, 2010 at 21:00
• I never realized it was named after Larry Page. I always assumed the name had something to do with Web Pages. Commented Nov 19, 2010 at 21:56
• @JohnFx Whoa, no kidding! Commented Nov 19, 2010 at 22:05
• +1: but can it qualify if the actual algorithm isn't known to humankind? (IIRC wikipedia's is an approximation) Commented Nov 21, 2010 at 1:52

Data compression algorithms

In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use, through use of specific encoding schemes.

• Exactly and I think the basic compression algorithm LZW can be considered one of the most beautiful algorithms in software engineering. Commented Nov 20, 2010 at 16:10
• "if possible give the name of the specific algorithm"
– user1249
Commented Dec 17, 2010 at 18:59

## Smith-Waterman (and Needleman-Wunsch)

This may be too far fetched so please comment.

### Smith-Waterman: The Sequence Alignment Algorithm

I think one of such examples is the Smith-Waterman and Needleman-Wunsch algorithms and their approximations. All of them are essentially doing the same thing: they align two or more strings (sequences). There is a significance in Biology. When DNA or Protein sequences are aligned - regions of structural, functional and evolutionary similarity are revealed.

### BLAST as a descendant of Smith-Waterman

A heuristic that approximates Smith-Waterman is BLAST. It allows searching sequences of large databases for Biological similarity. The popularity of BLAST is really great - it's very likely the most widely used algorithm in Biology. The newer areas in Bioinformatics and Genomics have newer and better approximations of Smith-Waterman/Needleman-Wunsch algorithms that are more accurate than BLAST.

### Genome Assembly as a descendant of Smith-Waterman

High-throughput approximations of Smith-Waterman and Needleman-Wunsch that are faster than BLAST are used to assemble Genomes from shotgun sequencing - where the product of the sequencer machine is a huge amount DNA reads (billions) from arbitrary parts of the Genome that are very short (50 to 100 nucleotides). The approach was used to complete the Human Genome Project. All modern sequencing is done this way.

### Multiple Sequence Alignment an extension of Smith-Waterman

Numerous Multiple Sequence Alignment algorithms exist - they are approximating a multi-sequence version of the Smith-Waterman/Needleman-Wunsch. Multiple sequences are aligned as a group simultaneously to each other. It's a much harder problem than it's pairwise counterpart, but the solutions provide much more insight into Biological function, structure, and evolutionary history of related sequences.

• Hello and welcome to Programmers! You might want to break up this answer into one for each of the algorithms you're presenting here as per it is customary for list questions like this to facilitate voting and sorting. Commented Nov 20, 2010 at 10:28
• @Yi Jiang: My pantheon! I misread your comment as "facilitate vomiting". :-/ Commented Nov 20, 2010 at 12:14
• Here I argue for only one algorithm - Smith-Waterman (and it's variant Needleman-Wunsch) Commented Nov 20, 2010 at 22:28

Siam named the following as the most important algorithms of the 20th century:

1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an efficient way to stumble toward answers to problems that are too complicated to solve exactly.

1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making.

1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation.

1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra.

1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code.

1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical.

1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases.

1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components.

1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers.

1987: Fast Multipole Method. A breakthrough in dealing with the complexity of n-body calculations, applied in problems ranging from celestial mechanics to protein folding.

Personally I would replace Integer Relation Detection with PageRank.

PageRank, love it or hate it, but it affects decisions and actions of millions people worldwide googling on a daily basis.

If I had to list the top 3 most important algorithms in use today in computers, I would say:

The Binary Search algorithm is used constantly to narrow down on an item within a sorted list, most index lookups will use something along these lines at some point. This algorithm provides a search of an ordered list in o(log n) time.

The Quicksort algorithm finally managed to get sort down to O(n log n) average case and O(n^2) worse case. Sorting is one of the most common data tasks in a computer and one of the most expensive, improving the average case sort was a huge step forward in efficiency.

Dijkstra's algorithm as has been said produces a shortest path between points within a graph. This is used widely for all manner of routing applications, most extensively with regard to the internet itself ensuring that the quickest path through the tangled web of interconnected routers is used.

• Binary search would have to be very, very old... I mean, it was formulated 'in the past' and it was in a 'decade', but it would have been around for many hundreds of years. Commented Feb 13, 2011 at 9:57
• @Kirk Broadhurst: Still, it is an incredibly important algorithm for computers. Regardless of when a human first conceived it. Commented Feb 13, 2011 at 13:39

Bayes' Theorem

It has probably contributed the most to keeping the amount of time-wasting spam in my inbox to a manageable level.

Of course, I'm it has been used in numerous other worthwhile applications, but SPAM-killing is my favorite.

• I would give you thumb up, but this is a theorem (one of the best) and not an algorithm. However many algorithms are based on this theorem. Commented Nov 19, 2010 at 21:56
• I was just trying to lump them all into a general category of algorithms, but technically you are correct. Commented Nov 19, 2010 at 21:58
• @AmirR Technically correct, the best kind of correct! Commented Nov 19, 2010 at 22:02

TimSort

This is the sorting algorithm now used in Python, Java 7 and Android

Basically:

• O(N log N) worst case (does not degenerate)
• O(N) for almost sorted list (in fact `N-1` exactly on already sorted list)

And the beauty of it ? It's stable! And therefore suitable for multipass sorting according to various criterion.

By the way, if anyone has an optimized C++ implementation on hand...

• It can't be Θ(NlogN), as it has that better behavior on an already sorted list. O(NlogN) is the right notation here. Commented May 28, 2011 at 11:30
• While this one is nice, I'd certainly not call it "one of the greatest algorithms invented in the past decades". Mergesort, upon which Timsort is based, is the real achievement. Commented May 29, 2011 at 7:03

All algorithms which used for solving Visibility Problem in 3D Computer Animation seems crucial to me.

Painter's algorithm

The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics. When projecting a 3D scene onto a 2D plane, it is necessary at some point to decide which polygons are visible, and which are hidden.

Z-buffering

In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional (3-D) graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which are hidden. The painter's algorithm is another common solution which, though less efficient, can also handle non-opaque scene elements. Z-buffering is also known as depth buffering.

Hidden surface determination

In 3D computer graphics, hidden surface determination (also known as hidden surface removal (HSR), occlusion culling (OC) or visible surface determination (VSD) is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. A hidden surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. The analogue for line rendering is hidden line removal. Hidden surface determination is necessary to render an image correctly, so that one cannot look through walls in virtual reality, for example.

Whichever one you need to solve your current problem.

• That's what I was going to say. Now I don't have to say it. Commented Nov 19, 2010 at 20:43
• Whichever is not a good answer. Whichever algorithms are not significant for humankind. Commented Nov 19, 2010 at 21:02
• This is not a specific algorithm and even if it were it probably isn't important to humankind. Commented Nov 19, 2010 at 21:04

Soundex is a phonetic algorithm for indexing names by sound.

• How did soundex contributed to humankind ? Commented Nov 21, 2010 at 11:10
• It improved the ability to use natural language, correcting for minor differences in spelling and regional pronunciation.
– sal
Commented Nov 23, 2010 at 15:21

Viterbi algorithm

Originally used to decode convolutional error-correcting codes, it is now used to solve a wide class of recognition problems (ranging from speech recognition to bioinformatics). You can find it in several communication and storage devices.

• +1 Viterbi algorithm is very important. @[Giacomo Verticale] perhaps you should mention it's relationship to Hidden Markov Models (HMMs). Commented Nov 28, 2010 at 5:48

MP3

Although it is a more general term than a specific algorithm, I'd mention MP3 as the aggregation of the different algorithms and techiques which work in cooperation to generate this lossy audio format.

It has surely been very significant in the "digital era".

Runge-Kutta numerical integration. Without it many simulations would not be possible. No space program, no nuclear power, no ballistics, no sports simulations, no bullet proof vests, no crash test simulation, no fluid motion simulation, no chemical interaction simulations, no earthquake resistant buildings ... the list goes on.

• +1 @j172 I know this one, it's really useful in numerical analysis and simulations. Commented May 28, 2011 at 6:19

Sorting algorithm.

• this isn't a specific algorithm, though... Commented Nov 20, 2010 at 1:05
• Yeah, what Justin L. said, which sorting algorithm? Commented Nov 20, 2010 at 12:09
• The "Specific algorithm" should be mergesort, the first of the n lg n sorts. Commented Nov 20, 2010 at 16:03
• @dr Hannibal Lecter: Bubble Sort of course. Everything else is premature optimization. Commented Nov 20, 2010 at 16:12
• Yuck! I certainly hope people aren't using quicksort in production code. More importantly mergesort came earlier and is almost as fast. (Hopefully most code uses some variant on Introsort) Commented Nov 20, 2010 at 1:07
• @Billy ONeal, sorting in .NET is all Quicksort. So, any program that calls List<T>.Sort() uses quicksort in production. Commented Nov 21, 2010 at 1:43
• @SnOrfus: Do you have proof of that statement? To my understanding List<t>.Sort is based on introsort. Commented Nov 21, 2010 at 1:53
• @Billy ONeal: straight from msdn - msdn.microsoft.com/en-us/library/b0zbh7b6.aspx Commented Nov 21, 2010 at 2:43
• @Thorbjørn: It's still not a good general purpose algorithm. Introsort is quicksort, but it switches to heap sort if it goes beyond a given recursion depth. This allows one to have the good characteristics of quicksort but always avoids the pathological cases, even if the algorithm chooses bad pivots. Commented Nov 26, 2010 at 21:08

Insertion Sort

Easy to implement, very fast on small lists and used in Merge Sort / Quicksort implementations to speed them up. It's stable, and operates in O(n) on sorted lists (when sorted in ascending order).

Gauss-Jordan in matrix computation

## Kalman Filter

It gets heavily used in navigation, target tracking (for almost any sensor: radar, sonar, FLIR, ladar). One textbook shows an application in a disk drive controller. Robotic control systems frequently use Kalman filters.

Spoken and Written language.

They are currently one of the most efficient algorithm to transfer knowledge from one thing to another. Without language, civil society could not exist, and information could not be conveyed.

• -1: Algorithms can be expressed using natural language, but natural languages are not algorithms. Commented Nov 21, 2010 at 1:47
• Would you say compression algorithms are not algorithms then? All language does is compress information that is conveyed from a source to a receptical. It has specific rules that have to be followed (grammar) just like any other algorithm, and it takes an input (your experiences) and produces a different output (knowledge). I fail to see how you could not consider language an algorithm. Commented Nov 21, 2010 at 15:41
• It fails all the standard definitions of algorithm on many fronts. Commented Dec 21, 2010 at 3:42

The heap data structure and its associated algorithms for heap construction and maintenance.

And show some respect for quicksort. Even if it is not always the sort of choice, it is one of the fundamental algorithms in the historical development of computer science, and is a great vehicle for understanding recursion and algorithm analysis. It is beautiful, and yes, I love it.

Indexing algorithms like B-tree,B+-tree,hash index,binary tree index etc. To index huge amount of data.

MapReduce as a way to divide, conquer and parallelize processing of large data sets.

Brute Force Algorithm !

Many people underestimate this brute force algorithm. Actually it is mostly used to solve problems having no pattern. I love it much!

• That's not an algorithm. It's a kind of algorithms. Commented Dec 16, 2010 at 16:32
• It's a method for breaking encryption. Commented Dec 21, 2010 at 7:14
• I think it is also categorized as an algorithm. "Start from x to y do something." <--- algorithm right? Commented Dec 21, 2010 at 7:38
• An algorithm is a series of steps to accomplish a specific task. That isn't specific.
– Anto
Commented May 25, 2011 at 18:35

Bubble Sort !

Bubble sort is not as bad as Bogosort. That is why I vote for the Bubble sort.

• Please consider to state why the algorithm is significant and important, people seem to just disagree over why Bubble Sort might be significant and important. Commented Dec 20, 2010 at 22:17
• Even Barack Obama knows bubble sort is the wrong way to go. Commented Dec 21, 2010 at 3:11
• @TomWij, @Joey: see my update. Commented May 29, 2011 at 3:16