40

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

Tamara Wijsman
  • 8,259
  • 14
  • 58
  • 94
Amir Rezaei
  • 10,938
  • 6
  • 61
  • 86
  • I haven't any idea of how I could actually answer the question. – David Thornley Nov 19 '10 at 20:37
  • I'm assuming you are talking purely about programming algorithms.... – Kavet Kerek Nov 19 '10 at 20:46
  • Why is this question getting Closed? – Amir Rezaei Nov 19 '10 at 21:17
  • 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
  • People who are answering think they know. Wouldn’t RSA and PageRank not be important? – Amir Rezaei Nov 19 '10 at 21:42
  • 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 07:46
  • 1
    Why do you answer your own questions? Several times? –  Nov 26 '10 at 21:04
  • @Thorbjørn- yea, i thought that too... but they're good answers. Also, he was probably just trying to show that it could be answered and it was a real question. – Derek Adair Dec 15 '10 at 00:02
  • @Thorbjørn Good Point! Since questions often gets misunderstanded here. @Thorbjørn Ravn Andersen The goal was to get a list; therefor I added one algorithms per answer. – Amir Rezaei Dec 17 '10 at 19:32
  • The fast inverse polynomial sieve, an O(n⁶) [integer factorization](http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity) algorithm for classical computers. Oh wait, you said *past* decades. – Joey Adams Dec 21 '10 at 03:01
  • So let me understand this... you asked a question at 11.19.2010 - 20:27 and then proceeded to answer that same very question at 20:39, 20:46, 22:27, 21:23. I am having trouble understanding can you explain this. You didn't just answer your own question, you answered it 4 times over. Clearly you did not need to ask such a question if you are already so familiar with algorithms. – Chris Jan 12 '11 at 11:54
  • 1
    @Chris Please read the question "I would like to **get a list** of the most important ones, **only one algorithm per answer** ." – Amir Rezaei Jan 12 '11 at 11:59
  • So make this a community wiki and start your list within the question. Answer your own question 4 times in an hour after it was asked leaves no one else a chance to answer. The information may be useful to someone but it seems to me at face value all you did here was attempt to gain a bunch of reputation by asking a question and then answering it. I can read that, if you already have a started said list then that should be posted in the question to suggest what you are already aware of or considering. Just my two cents. If you did this on stackoverflow you would be chastised. – Chris Jan 12 '11 at 14:34
  • @Chris First if I listed the algorithm under the question then I wouldn't get them ranked. Second I don’t get any reputation point on my own answers. – Amir Rezaei Jan 12 '11 at 14:38
  • You more certainly do get reputation for answering your own question. I just down voted you and you lost 2 points, I just upvoted and you gained 10 points + 2 lost from the down vote. Goto your profile and check reputation and you will certainly see reputation points contributed to you for your answers to your own question. I am not here to argue I am just pointing out that this seems a bit peculiar. – Chris Jan 12 '11 at 14:39
  • @Chris I didn't noticed that when I ask the question. Did you down vote my answer or question? – Amir Rezaei Jan 12 '11 at 14:42
  • Answer which dropped your 2, then upvoted which brought your 2 points lost back and then added +10 for the upvote. Regardless, I do not care one way or the other, I am just pointing it out for the betterment of the community. – Chris Jan 12 '11 at 16:32
  • 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

28 Answers28

59

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

Jeremy
  • 4,609
  • 22
  • 22
37

Dijkstra's algorithm

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

Amir Rezaei
  • 10,938
  • 6
  • 61
  • 86
  • 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. –  Nov 19 '10 at 23:41
  • 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 01:06
  • @Billy, where exactly would you expect that the Dijkstra algorithm is actually used and by whom? –  Nov 20 '10 at 07: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. – Billy ONeal Nov 20 '10 at 15:59
  • 3
    @Billy, but my objection was to "exists in _EVERY_ router in the world". That is - in my opinion - plainly wrong. –  Nov 26 '10 at 21:05
  • @Thorbjorn: Good point :) – Billy ONeal Nov 26 '10 at 21:09
30

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.

Amir Rezaei
  • 10,938
  • 6
  • 61
  • 86
  • 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
26

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.

Amir Rezaei
  • 10,938
  • 6
  • 61
  • 86
22

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.

Amir Rezaei
  • 10,938
  • 6
  • 61
  • 86
  • 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
  • "if possible give the name of the specific algorithm" –  Dec 17 '10 at 18:59
14

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.

Aleksandr Levchuk
  • 191
  • 7
  • 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. – Yi Jiang Nov 20 '10 at 10:28
  • @Yi Jiang: My pantheon! I misread your comment as "facilitate vomiting". :-/ – dr Hannibal Lecter Nov 20 '10 at 12:14
  • Here I argue for only one algorithm - Smith-Waterman (and it's variant Needleman-Wunsch) – Aleksandr Levchuk Nov 20 '10 at 22:28
13

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.

jason
  • 220
  • 1
  • 5
  • 1
    To this list, I'd add 2 books, although they were more about "most important theorems" of the 20th century: Five Golden Rules http://www.amazon.com/Five-Golden-Rules-20th-Century-Mathematics/dp/0471193372 , and Five More Golden Rules. http://www.amazon.com/Five-More-Golden-Rules-20th-Century/dp/0471395285/ – Tangurena Nov 19 '10 at 22:21
  • Monte Carlo techniques are still used, more or less in the original form. This is also true of the FFT and Quicksort. Most of the rest I'm simply not familiar with. The Simplex method for LP doesn't scale at all well, compared to more modern methods. – David Thornley Dec 16 '10 at 19:30
9

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

Maksee
  • 2,653
  • 1
  • 16
  • 12
9

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.

Orbling
  • 5,696
  • 1
  • 32
  • 38
  • 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. – Kirk Broadhurst Feb 13 '11 at 09:57
  • @Kirk Broadhurst: Still, it is an incredibly important algorithm for computers. Regardless of when a human first conceived it. – Orbling Feb 13 '11 at 13:39
8

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.

JohnFx
  • 19,052
  • 8
  • 65
  • 112
  • 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. – Amir Rezaei Nov 19 '10 at 21:56
  • I was just trying to lump them all into a general category of algorithms, but technically you are correct. – JohnFx Nov 19 '10 at 21:58
  • @AmirR Technically correct, the best kind of correct! – Mark C Nov 19 '10 at 22:02
7

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

Matthieu M.
  • 14,567
  • 4
  • 44
  • 65
  • It can't be Θ(NlogN), as it has that better behavior on an already sorted list. O(NlogN) is the right notation here. – Donal Fellows May 28 '11 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. – Billy ONeal May 29 '11 at 07:03
6

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.

bman
  • 141
  • 4
3

Whichever one you need to solve your current problem.

mipadi
  • 7,493
  • 36
  • 35
3

Soundex is a phonetic algorithm for indexing names by sound.

sal
  • 2,078
  • 1
  • 15
  • 19
3

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.

Giacomo Verticale
  • 131
  • 2
  • +1 Viterbi algorithm is very important. @[Giacomo Verticale] perhaps you should mention it's relationship to Hidden Markov Models (HMMs). – Aleksandr Levchuk Nov 28 '10 at 05:48
3

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

Jens Hoffmann
  • 131
  • 2
3

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.

John Alexiou
  • 153
  • 1
  • 4
2

Sorting algorithm.

tia
  • 965
  • 5
  • 9
2

Quicksort

ysolik
  • 6,340
  • 4
  • 34
  • 50
  • 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 01:07
  • 2
    @Billy ONeal, sorting in .NET is all Quicksort. So, any program that calls List.Sort() uses quicksort in production. – Steven Evers Nov 21 '10 at 01:43
  • @SnOrfus: Do you have **proof** of that statement? To my understanding List.Sort is based on introsort. – Billy ONeal Nov 21 '10 at 01:53
  • 3
    @Billy ONeal: straight from msdn - http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx – ysolik Nov 21 '10 at 02:43
  • @ysolik: Huh. That really sucks :( – Billy ONeal Nov 21 '10 at 07:55
  • @Billy, the crucial point is the pivot element selection. If bad, quicksort is O(n^2), if good quicksort is O(n log n). –  Nov 26 '10 at 21:07
  • 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
  • @Thor: The lack of stability is a big issue in practice. It's possible to work around it of course (e.g., with a more complex comparison term that uses the initial position as a minor discriminant) but that consuming additional working space, destroying quicksort's memory advantage over mergesort… – Donal Fellows May 28 '11 at 11:35
1

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

Oliver Weiler
  • 2,448
  • 19
  • 28
1

Gauss-Jordan in matrix computation

Second Person Shooter
  • 160
  • 1
  • 2
  • 11
1

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.

John R. Strohm
  • 18,043
  • 5
  • 46
  • 56
0

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.

Malfist
  • 3,641
  • 5
  • 29
  • 40
  • 5
    -1: Algorithms can be expressed using natural language, but natural languages are not algorithms. – Steven Evers Nov 21 '10 at 01: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
  • It fails all the standard definitions of algorithm on many fronts. – President James K. Polk Dec 21 '10 at 03:42
0

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.

President James K. Polk
  • 101
  • 2
0

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

xyz
  • 1,152
  • 1
  • 9
  • 14
0

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

Jay Elston
  • 2,680
  • 22
  • 30
-1

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!

Second Person Shooter
  • 160
  • 1
  • 2
  • 11
-5

Bubble Sort !

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

Second Person Shooter
  • 160
  • 1
  • 2
  • 11