19

Which algorithms are used most often?

Please write a single algorithm per answer, try to keep your answer short (one or two lines).

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • Kaveh, maybe you should wait for responses before supplying so many ? :) – Suresh Venkat Sep 03 '10 at 22:36
  • 1
    @Suresh: Sorry. :) – Kaveh Sep 03 '10 at 22:44
  • 3
    Most often in what sense? (Number of different computer programs that implement the algorithm? Number of installed pieces of software that use the algorithm? Number of executions of the algorithm? Amount of data processed by using the algorithm? CPU seconds used by the algorithm?) Where? (Academia, industry, home PCs?) Is it ever possible to estimate anything like this; can we have ever any data to back any of the answers? – Jukka Suomela Sep 03 '10 at 22:45
  • Another criterion I'd add to Jukka's list is most often implemented (preferably excluding schoolwork): these would be the algorithms that most need to be taught. – Gilles 'SO- stop being evil' Sep 04 '10 at 10:01
  • 1
    The question is too vague as Jukka Suomela pointed out. Without further clarification, the answers will be no better than the table of contents of a textbook on algorithms. – Tsuyoshi Ito Sep 11 '10 at 20:50
  • @Tsuyoshi: Sorry for not clarifying my question earlier. Some of the senses mentioned above are interesting in their own, but what I really had in my mind was the most common algorithms not in any formal sense (like the number of programs using them), but rather the algorithms that people feel are used most often. I was trying to come up with a nice algorithmic name that most people would like to associate with this site. I think it is close to other senses mentioned above specially the one that Gilles has mentioned. – Kaveh Sep 13 '10 at 00:59
  • Algorithms which people feel are used most often and most need to be taught? That really sounds like a table of contents of a textbook on algorithms. – Tsuyoshi Ito Sep 13 '10 at 02:21
  • Well then, Tsuyoshi, name the one you would teach if you could teach one algorithm to everybody on this planet, but only this one. – Raphael Oct 08 '10 at 09:55
  • @Juan, it has been a while but I think Raphael's comment is probably the one that captures my intention at the time of posting it. (I agree that this was not a very good question, it was posted in the early months of the site). – Kaveh Jan 16 '12 at 20:12
  • 1
    There is a recent book: "Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers" by John MacCormick. See http://press.princeton.edu/titles/9528.html – Alessandro Jacopson Jan 25 '12 at 17:53

22 Answers22

18

Is the Fast Fourier Transform the algorithmic problem solved most times per day by real computer systems? It has to be close. So I'd nominate the Cooley-Tukey FFT algorithm.

Aaron Sterling
  • 6,994
  • 6
  • 42
  • 74
  • I like this, FFT is overlooked in basic computer science education, but it is certainly an algorithm with a tremendous impact in our modern society, and many modern things around us are crunching FFT all the time. – Jukka Suomela Sep 04 '10 at 10:27
14

Multiplication.

Perhaps one of the oldest not-entirely-trivial algorithms, and a problem that is solved more often than FFT.

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
  • Multiplication isn't an algorithm, it's a problem with many subproblems solved by different algorithms: fixed-size integer and floating-point, performed by hardware or software; variable-size bignums (modulo or not), matrices, ... – Gilles 'SO- stop being evil' Sep 04 '10 at 09:58
  • I was referring to the hardware multiplication circuits in modern CPUs (for integers and floating-point numbers; these two aren't that different in the end). My understanding is that they tend to be "just" very cleverly engineered versions of the same basic approach – the "long multiplication" algorithm, which was already known in the Middle Ages. – Jukka Suomela Sep 04 '10 at 10:13
  • I think that subtraction (comparison) is used much more often than multiplication, and I cannot see any reason why multiplication counts as an algorithm and addition/subtraction does not. However, I do not know if this qualifies as an answer. – Tsuyoshi Ito Sep 12 '10 at 18:08
  • Yes, addition and subtraction are used even more often than multiplication – indeed, the long multiplication algorithm essentially reduces a multiplication to an addition. However, I don't know if there is a single addition/subtraction algorithm that we could nominate here? – Jukka Suomela Sep 12 '10 at 21:02
  • @JukkaSuomela: Two's complement addition and subtraction would be a good candidate. – John Gietzen Jan 16 '12 at 13:57
13

Dijkstra and Bellman-Ford shortest path algorithms. There are at least 35,000 Autonomous Systems (AS) active on the Internet as of 2010. Each AS is running either a link-state routing protocol (Dijkstra) or a distance-vector routing protocol (Bellman-Ford). The routers within one AS typically update their tables periodically every few minutes, say 10.

Thus, the number of Dijkstra & Bellman-Ford executions per day amounts to at least 5 million. And that's only from the routers.

We have not counted shortest path computations from Google Maps and the likes which should easily account for 10 times as many. Half a billion executions a day is not far-fetched.

Hung Q. Ngo
  • 311
  • 3
  • 7
  • Half a billion executions a day may sound like a lot, but let's keep in mind that we have, e.g., billions of mobile phones on this planet. What are those things doing all the time? Or what are they doing during each phone call? I don't know, but my guess is that they are at the very least doing a lot more of FFT than shortest paths. – Jukka Suomela Sep 04 '10 at 10:24
8

Quicksort

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • 14
    By the way, is it really the case that quicksort is the sorting algorithm that is used most commonly in the real world? I had a quick look at the implementation of a general-purpose "sort" function in some commonly used programming languages. Perl: seems to have switched from quicksort to mergesort recently. Python: uses Timsort (mergesort/insertion sort hybrid). Java: used to be mergesort, nowadays Timsort. Databases tend to use external sorting. Is quicksort already an endangered species? – Jukka Suomela Sep 03 '10 at 23:05
  • I think that is a very good point. It would be great if someone can edit the answer. – Juan Bermejo Vega Jan 16 '12 at 10:51
  • @Juan, although the point Jukka mentioned is correct I don't see any reason to edit the answer. – Kaveh Jan 16 '12 at 20:09
7

I think the most used algorithm is Parity Check (or maybe CRC or some kind of error-correcting code), because they appear in every RAM access.

didest
  • 1,551
  • 16
  • 25
7

Binary Search

Kaveh
  • 21,577
  • 8
  • 82
  • 183
5

Simplex Algorithm - isn't this still competitive with the best interior point methods? If so it has to be used a lot.

Mugizi Rwebangira
  • 1,278
  • 10
  • 18
4

$k$-means..

More generally, you should look at the Kanellakis prize winners for ideas that have theoretical and practical heft.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • thank you for the link, it looks very interesting. Partial motivation for the question was finding a nice catchy algorithmic name for the site. :) – Kaveh Sep 03 '10 at 22:37
4

Regular expression matching by conversion to finite automata - I believe grep functions along these lines.

Neeldhara
  • 599
  • 2
  • 15
3

Depth First Search (DFS)

Kaveh
  • 21,577
  • 8
  • 82
  • 183
3

It's hard to think of more widely used algorithms than those in modern implementations of TCP: ie congestion avoidance, fast retransmit. Though that depends on how one determines what meets the criteria for an algorithm...

Lev Reyzin
  • 11,968
  • 13
  • 63
  • 103
  • But can you really use TCP algorithms more often than FFT (which is already on this list)? If my computer sends a single IP packet (TCP or not), doesn't it typically trigger a whole bunch of FFT calculations? Usually the packets are transmitted at some point by using technologies such as WLAN, ADSL, and GSM, and I think most of them use modulations that rely heavily on FFT. – Jukka Suomela Sep 04 '10 at 09:34
  • I think you're right. – Lev Reyzin Sep 04 '10 at 12:45
3

Gaussian Elimination This is still used in practice right? If not replace with whatever is most frequently used to solve linear systems...

Mugizi Rwebangira
  • 1,278
  • 10
  • 18
2

B+ tree related algorithms is used in for the database stuffs

Prabu
  • 467
  • 2
  • 14
2

Scheduling algorithms. They are used by every user device and server worldwide. A number of variations is being used, I found a lot of references for "multilevel feedback queue"

chazisop
  • 3,796
  • 2
  • 29
  • 37
2

SHA-1 (and hash functions in general). Probably beat most other algorithms in terms of the number of executions.

Hung Q. Ngo
  • 311
  • 3
  • 7
1

This response interprets "most often" in terms of actual CPU cycles.

When I was learning computing in the '70s I recall reading that the vast majority of computer (read: mainframe) cycles were devoted to sorting. Business applications demand extensive sorting for analysis and reporting. I don't imagine that has changed very much, but of course the rise of other apps--e-mail, word processing, etc.--must have altered the mix. Those sorts are usually stable sorts (not Quicksort) due to the need to sort on successions of fields to create subsorts.

Strictly speaking, though, the algorithm used the most often is, without any doubt, whatever is executed by the Windows system wait process when nothing else otherwise is going on ;-).

whuber
  • 354
  • 1
  • 9
1

Sprase Matrix Vector Multiply

... is the computational workhorse behind the solution of almost all linear systems. As a result it is being run whenever

  • Scientists/engineers solve differential equations
  • Statisticians find new correlations (PCA)
  • Google runs pagerank
  • Your phone predicts your location from GPS, accelerometers, cell tower locations
  • Your car adjusts your suspension in motion
  • etc....

Most of the FLOPs on any supercomputer or cluster are spent inside of a sparse mat-vec.

MRocklin
  • 101
  • 3
1

Newton's method. It's used for computing square roots, for computing division. It can be used to do linear programming. More generally it's the workhorse of (convex) optimization. It can be used to solve differential equations in Physics by minimizing the action/energy.

Jules
  • 390
  • 1
  • 10
1

Hashing and red-black trees.

They're already implemented in STL (hash_map, map), and every programmer knows that such a container is incredibly convenient whenever you want to store some information indexed by an arbitrary data type.

zotachidil
  • 622
  • 7
  • 14
1

Error correction algorithms, such as Reed-Solomon.

http://en.wikipedia.org/wiki/Error-correcting_code#List_of_error-correcting_codes http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

Christian Kohlschütter
  • 101
  • 1
0

String Matching, used all the time in application software and on database level.

In the exact case, there are several quite involved algorithms (KMP, Boyer-Moore) with some that achieve sublinear expected runtime. They are also interesting to study from a CS point of view.

Approximate string matching, that is alignments, is probably even more interesting. You know "autocorrecting" features? Also, searches in noisy string data (e.g. DNA) is done using alignments.

Raphael
  • 4,565
  • 28
  • 48
0

Dynamic Programming.

I think DP is used "more often" than other algorithms cited in the survey so far. I infer "more often" in the sense of how often a non-trivial algorithm concept was implemented by programmer in real-life, rather than how many time a particular implementation of an algorithm in invoked.

DP is versatile, and has many faces. Sometimes I used it somewhat subconsciously and then realized later I was doing DP.

Of course, there are things that are even more common than Dynamic Program, but they are mostly data structure (array, linked list, hash).

Hardy Leung
  • 151
  • 6
  • 7
    This is a bit different from the other suggestions as it is an algorithm design paradigm (similar to greedy or primal-dual) and not just a single algorithm. – Jukka Suomela Sep 04 '10 at 10:31