Which algorithms are used most often?
Please write a single algorithm per answer, try to keep your answer short (one or two lines).
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
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.
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.
Simplex Algorithm - isn't this still competitive with the best interior point methods? If so it has to be used a lot.
Depth First Search (DFS)
Gaussian Elimination This is still used in practice right? If not replace with whatever is most frequently used to solve linear systems...
SHA-1 (and hash functions in general). Probably beat most other algorithms in terms of the number of executions.
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 ;-).
Sprase Matrix Vector Multiply
... is the computational workhorse behind the solution of almost all linear systems. As a result it is being run whenever
Most of the FLOPs on any supercomputer or cluster are spent inside of a sparse mat-vec.
Error correction algorithms, such as Reed-Solomon.
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).
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.