Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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...

share

locked by Yannis Rizos Apr 28 '13 at 11:48

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site, so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. More info: help center.

closed as not constructive by Anna Lear Nov 12 '11 at 6:29

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
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. –  David Thornley Nov 19 '10 at 21:40
2  
It might be off-topic, but its a real question. –  Jeremy Nov 19 '10 at 22:32
1  
+1 Good question. I suggest re-asking this on cstheory.stackexchange.com –  Aleksandr Levchuk Nov 21 '10 at 7:46
1  
Why do you answer your own questions? Several times? –  user1249 Nov 26 '10 at 21:04
2  
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. –  Aaronaught May 27 '11 at 21:17
show 15 more comments

28 Answers 28

up vote 59 down vote accepted

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

share
4  
+1 and to add to your answer, RSA. –  sange Nov 19 '10 at 20:45
show 1 more comment

Dijkstra's algorithm

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

share
2  
@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. –  Billy ONeal Nov 20 '10 at 1:06
3  
@Billy, but my objection was to "exists in EVERY router in the world". That is - in my opinion - plainly wrong. –  user1249 Nov 26 '10 at 21:05
show 4 more comments

Fast Fourier transform (FFT)

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.

share
4  
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. –  Dan Ray Nov 24 '10 at 13:10
add comment

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.

share
36  
I never realized it was named after Larry Page. I always assumed the name had something to do with Web Pages. –  JohnFx Nov 19 '10 at 21:56
1  
@JohnFx Whoa, no kidding! –  Mark C Nov 19 '10 at 22:05
show 3 more comments

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.

share
2  
Exactly and I think the basic compression algorithm LZW can be considered one of the most beautiful algorithms in software engineering. –  mojuba Nov 20 '10 at 16:10
show 1 more comment

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.

share
show 3 more comments

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.

share
1  
To this list, I'd add 2 books, although they were more about "most important theorems" of the 20th century: Five Golden Rules amazon.com/Five-Golden-Rules-20th-Century-Mathematics/dp/… , and Five More Golden Rules. amazon.com/Five-More-Golden-Rules-20th-Century/dp/0471395285 –  Tangurena Nov 19 '10 at 22:21
show 1 more comment

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

share
add comment

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

  1. Binary Search
  2. Quicksort
  3. Dijkstra's algorithm

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.

share
show 3 more comments

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.

share
show 3 more comments

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...

share
show 3 more comments

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.

share
add comment

Whichever one you need to solve your current problem.

share
1  
That's what I was going to say. Now I don't have to say it. –  Robert Harvey Nov 19 '10 at 20:43
6  
This is not a specific algorithm and even if it were it probably isn't important to humankind. –  Jason Nov 19 '10 at 21:04
show 1 more comment

Soundex is a phonetic algorithm for indexing names by sound.

share
show 2 more comments

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.

share
show 1 more comment

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".

share
add comment

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.

share
show 1 more comment

Sorting algorithm.

share
1  
+1 because they get used billions of times per day –  Barry Brown Nov 19 '10 at 21:05
5  
this isn't a specific algorithm, though... –  Justin L. Nov 20 '10 at 1:05
2  
@dr Hannibal Lecter: Bubble Sort of course. Everything else is premature optimization. –  peterchen Nov 20 '10 at 16:12
show 2 more comments

Quicksort

share
1  
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) –  Billy ONeal Nov 20 '10 at 1:07
2  
@Billy ONeal, sorting in .NET is all Quicksort. So, any program that calls List<T>.Sort() uses quicksort in production. –  Steve Evers Nov 21 '10 at 1:43
3  
@Billy ONeal: straight from msdn - msdn.microsoft.com/en-us/library/b0zbh7b6.aspx –  ysolik Nov 21 '10 at 2:43
3  
@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. –  Billy ONeal Nov 26 '10 at 21:08
show 4 more comments

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).

share
add comment

Gauss-Jordan in matrix computation

share
add comment

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.

share
add comment

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.

share
5  
-1: Algorithms can be expressed using natural language, but natural languages are not algorithms. –  Steve Evers Nov 21 '10 at 1:47
2  
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. –  Malfist Nov 21 '10 at 15:41
show 1 more comment

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.

share
add comment

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

share
add comment

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

share
add comment

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!

share
5  
That's not an algorithm. It's a kind of algorithms. –  Anna Lear Dec 16 '10 at 16:32
show 3 more comments

Bubble Sort !

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

share
1  
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. –  Tom Wijsman Dec 20 '10 at 22:17
5  
Even Barack Obama knows bubble sort is the wrong way to go. –  Joey Adams Dec 21 '10 at 3:11
show 1 more comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.