<p>Multiplication.</p>

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

CC BY-SA 3.0
2012-01-16T13:57:43.180Z
@JukkaSuomela: Two's complement addition and subtraction would be a good candidate.
John Gietzen
CC BY-SA 2.5
2010-09-04T09:58:19.987Z
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'
CC BY-SA 2.5
2010-09-04T10:13:36.887Z
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
CC BY-SA 2.5
2010-09-12T18:08:45.857Z
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
CC BY-SA 2.5
2010-09-12T21:02:40.233Z
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
CC BY-SA 2.5
2010-09-03T23:32:13.577Z
2010-09-03T23:32:13.577Z
Jukka Suomela
<p><a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="nofollow">Dijkstra</a> and <a href="http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm" rel="nofollow">Bellman-Ford</a> shortest path algorithms. There are <a href="http://www.potaroo.net/tools/asns/" rel="nofollow">at least</a> 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. </p>

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

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

CC BY-SA 2.5
2010-09-04T10:24:48.820Z
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
CC BY-SA 2.5
2010-09-04T00:28:40.490Z
2010-09-04T00:28:40.490Z
Hung Q. Ngo
<p><a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a></p>

CC BY-SA 3.0
2012-01-16T10:51:35.127Z
I think that is a very good point. It would be great if someone can edit the answer.
Juan Bermejo Vega
CC BY-SA 3.0
2012-01-16T20:09:53.633Z
@Juan, although the point Jukka mentioned is correct I don't see any reason to edit the answer.
Kaveh
CC BY-SA 2.5
2010-09-03T23:05:38.743Z
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
CC BY-SA 2.5
2010-09-03T22:34:54.940Z
2010-09-03T22:34:54.940Z
Kaveh
<p><a href="http://en.wikipedia.org/wiki/Binary_search_algorithm">Binary Search</a></p>

CC BY-SA 2.5
2010-09-03T22:29:35.853Z
2010-09-03T22:29:35.853Z
Kaveh
<p>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.</p>

CC BY-SA 2.5
2011-02-23T10:02:40.243Z
Also used at least once for every packet being sent across any IP-based network
Claus Broch
CC BY-SA 2.5
2010-10-08T07:34:34.740Z
2010-10-08T07:34:34.740Z
didest
<p><a href="http://en.wikipedia.org/wiki/Simplex_algorithm">Simplex Algorithm</a> - isn't this still competitive with the best interior point methods? If so it has to be used a lot.</p>

CC BY-SA 2.5
2010-09-04T04:05:37.550Z
2010-09-04T04:05:37.550Z
Mugizi Rwebangira
<p><a href="http://en.wikipedia.org/wiki/K-means_clustering" rel="nofollow">$k$-means.</a>. </p>

<p>More generally, you should look at the <a href="http://awards.acm.org/kanellakis/" rel="nofollow">Kanellakis prize winners</a> for ideas that have theoretical and practical heft. </p>

CC BY-SA 2.5
2010-09-03T22:37:50.363Z
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
CC BY-SA 2.5
2010-09-03T22:30:18.873Z
2010-09-03T22:30:18.873Z
Suresh Venkat
<p>Regular expression matching by conversion to finite automata - I believe grep functions along these lines.</p>

CC BY-SA 2.5
2010-09-04T03:55:41.883Z
2010-09-04T03:55:41.883Z
Neeldhara
<p><a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow">Depth First Search</a> (DFS)</p>

CC BY-SA 2.5
2010-09-03T22:27:44.080Z
2010-09-03T22:27:44.080Z
Kaveh
<p><a href="http://en.wikipedia.org/wiki/Gaussian_elimination" rel="nofollow">Gaussian Elimination</a> This is still used in practice right? If not replace with whatever is most frequently used to solve linear systems...</p>

CC BY-SA 2.5
2010-09-04T03:59:23.403Z
2010-09-04T03:59:23.403Z
Mugizi Rwebangira
<p>It's hard to think of more widely used algorithms than those in modern implementations of <a href="http://en.wikipedia.org/wiki/Transmission_Control_Protocol" rel="nofollow">TCP</a>:  ie <a href="http://en.wikipedia.org/wiki/TCP_congestion_avoidance_algorithm" rel="nofollow">congestion avoidance</a>, <a href="http://en.wikipedia.org/wiki/Fast_retransmit" rel="nofollow">fast retransmit</a>.  Though that depends on how one determines what meets the criteria for an algorithm...</p>

CC BY-SA 2.5
2010-09-04T09:34:08.723Z
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
CC BY-SA 2.5
2010-09-04T12:45:55.000Z
I think you're right.
Lev Reyzin
CC BY-SA 2.5
2010-09-04T01:37:41.073Z
2010-09-04T01:37:41.073Z
Lev Reyzin
<p>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"</p>

CC BY-SA 2.5
2010-09-12T08:28:39.280Z
2010-09-12T08:28:39.280Z
chazisop
<p>B+ tree related algorithms is used in for the database stuffs</p>

CC BY-SA 2.5
2010-09-11T17:19:20.830Z
2010-09-11T17:19:20.830Z
Prabu 
<p><a href="http://en.wikipedia.org/wiki/SHA-1" rel="nofollow">SHA-1</a> (and hash functions in general). Probably beat most other algorithms in terms of the number of executions.</p>

CC BY-SA 2.5
2010-09-03T22:55:40.677Z
2010-09-03T22:55:40.677Z
Hung Q. Ngo
<p>Error correction algorithms, such as Reed-Solomon.</p>

<p><a href="http://en.wikipedia.org/wiki/Error-correcting_code#List_of_error-correcting_codes" rel="nofollow">http://en.wikipedia.org/wiki/Error-correcting_code#List_of_error-correcting_codes</a>
http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction</p>

CC BY-SA 3.0
2012-01-16T08:03:00.860Z
2012-01-16T08:03:00.860Z
Christian Kohlschütter
<p>Hashing and red-black trees. </p>

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

CC BY-SA 3.0
2012-01-15T23:32:46.670Z
2012-01-15T23:32:46.670Z
zotachidil
<p>This response interprets "most often" in terms of actual CPU cycles.</p>

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

<p>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 ;-).</p>

CC BY-SA 2.5
2010-09-12T20:05:41.773Z
2010-09-12T20:05:41.773Z
whuber
<p>Sprase Matrix Vector Multiply</p>

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

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

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

CC BY-SA 3.0
2012-01-13T17:04:06.223Z
2012-01-13T17:04:06.223Z
MRocklin
<p>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.</p>

CC BY-SA 3.0
2012-01-14T01:18:02.567Z
2012-01-14T01:18:02.567Z
Jules
<p>String Matching, used all the time in application software and on database level.</p>

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

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

CC BY-SA 2.5
2010-10-08T09:52:30.937Z
2010-10-08T09:52:30.937Z
Raphael
<p><a href="http://en.wikipedia.org/wiki/Dynamic_Programming" rel="nofollow">Dynamic Programming</a>.</p>

<p>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 <em>implemented</em> by programmer in real-life, rather than how many time a particular implementation of an algorithm in invoked.</p>

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

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

CC BY-SA 2.5
2010-09-04T10:31:14.193Z
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
CC BY-SA 2.5
2010-09-04T03:50:20.457Z
2010-09-04T04:10:19.007Z
2010-09-04T04:10:19.007Z
Hardy Leung
<p>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 <a href="http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm" rel="nofollow">Cooley-Tukey FFT algorithm</a>.</p>

CC BY-SA 2.5
2010-09-04T10:27:25.077Z
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
CC BY-SA 2.5
2010-09-03T23:07:35.120Z
2010-09-03T23:07:35.120Z
Aaron Sterling
<blockquote>
  <p>Which algorithms are used most often?</p>
</blockquote>

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

CC BY-SA 3.0
2012-01-16T20:12:43.553Z
@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
CC BY-SA 3.0
2012-01-25T17:53:28.253Z
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
CC BY-SA 2.5
2010-09-03T22:36:06.900Z
Kaveh, maybe you should wait for responses before supplying so many ? :)
Suresh Venkat
CC BY-SA 2.5
2010-09-03T22:44:33.173Z
@Suresh: Sorry. :)
Kaveh
CC BY-SA 2.5
2010-09-03T22:45:45.377Z
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
CC BY-SA 2.5
2010-09-04T10:01:54.880Z
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'
CC BY-SA 2.5
2010-09-11T20:50:41.593Z
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
CC BY-SA 2.5
2010-09-13T00:59:12.860Z
@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
CC BY-SA 2.5
2010-09-13T02:21:51.320Z
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
CC BY-SA 2.5
2010-10-08T09:55:28.703Z
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
<ds.algorithms><big-list>
Which algorithms are used most often in practice?
Kaveh
# Which algorithms are used most often in practice?

(Asked by: username_0 on 2010-09-03)

> Which algorithms are used most often?

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

**Tags:** ds.algorithms, big-list
> **Comments:**
> **username_2**: Kaveh, maybe you should wait for responses before supplying so many ? :)  
> **username_0**: @Suresh: Sorry. :)  
> **username_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?  
> **username_4**: 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.  
> **username_5**: 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.  
> **username_0**: @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.  
> **username_5**: 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.  
> **username_6**: Well then, Tsuyoshi, name the one you would teach if you could teach one algorithm to everybody on this planet, but only this one.  
> **username_0**: @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).  
> **username_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  

---

## 22 answers

### Answer by username_23 on 2010-09-03. Score: 18 | Accepted answer

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](http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm).

> **Comments:**
> **username_3**: 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.  

---

### Answer by username_3 on 2010-09-03. Score: 14

Multiplication.

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

> **Comments:**
> **username_4**: 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, ...  
> **username_3**: 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.  
> **username_5**: 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.  
> **username_3**: 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?  
> **username_7**: @JukkaSuomela: Two's complement addition and subtraction would be a good candidate.  

---

### Answer by username_8 on 2010-09-04. Score: 13

[Dijkstra](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) and [Bellman-Ford](http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) shortest path algorithms. There are [at least](http://www.potaroo.net/tools/asns/) 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.

> **Comments:**
> **username_3**: 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.  

---

### Answer by username_0 on 2010-09-03. Score: 8

[Quicksort](http://en.wikipedia.org/wiki/Quicksort)

> **Comments:**
> **username_3**: 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?  
> **username_9**: I think that is a very good point. It would be great if someone can edit the answer.  
> **username_0**: @Juan, although the point Jukka mentioned is correct I don't see any reason to edit the answer.  

---

### Answer by username_0 on 2010-09-03. Score: 7

[Binary Search](http://en.wikipedia.org/wiki/Binary_search_algorithm)


---

### Answer by username_10 on 2010-10-08. Score: 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.

> **Comments:**
> **username_11**: Also used at least once for every packet being sent across any IP-based network  

---

### Answer by username_12 on 2010-09-04. Score: 5

[Simplex Algorithm](http://en.wikipedia.org/wiki/Simplex_algorithm) - isn't this still competitive with the best interior point methods? If so it has to be used a lot.


---

### Answer by username_2 on 2010-09-03. Score: 4

[$k$-means.](http://en.wikipedia.org/wiki/K-means_clustering).

More generally, you should look at the [Kanellakis prize winners](http://awards.acm.org/kanellakis/) for ideas that have theoretical and practical heft.

> **Comments:**
> **username_0**: thank you for the link, it looks very interesting. Partial motivation for the question was finding a nice catchy algorithmic name for the site. :)  

---

### Answer by username_13 on 2010-09-04. Score: 4

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


---

### Answer by username_0 on 2010-09-03. Score: 3

[Depth First Search](http://en.wikipedia.org/wiki/Depth-first_search) (DFS)


---

### Answer by username_12 on 2010-09-04. Score: 3

[Gaussian Elimination](http://en.wikipedia.org/wiki/Gaussian_elimination) This is still used in practice right? If not replace with whatever is most frequently used to solve linear systems...


---

### Answer by username_14 on 2010-09-04. Score: 3

It's hard to think of more widely used algorithms than those in modern implementations of [TCP](http://en.wikipedia.org/wiki/Transmission_Control_Protocol): ie [congestion avoidance](http://en.wikipedia.org/wiki/TCP_congestion_avoidance_algorithm), [fast retransmit](http://en.wikipedia.org/wiki/Fast_retransmit). Though that depends on how one determines what meets the criteria for an algorithm...

> **Comments:**
> **username_3**: 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.  
> **username_14**: I think you're right.  

---

### Answer by username_15 on 2010-09-12. Score: 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"


---

### Answer by username_16 on 2010-09-11. Score: 2

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


---

### Answer by username_8 on 2010-09-03. Score: 2

[SHA-1](http://en.wikipedia.org/wiki/SHA-1) (and hash functions in general). Probably beat most other algorithms in terms of the number of executions.


---

### Answer by username_17 on 2012-01-16. Score: 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


---

### Answer by username_18 on 2012-01-15. Score: 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.


---

### Answer by username_19 on 2010-09-12. Score: 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 ;-).


---

### Answer by username_20 on 2012-01-13. Score: 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.


---

### Answer by username_21 on 2012-01-14. Score: 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.


---

### Answer by username_6 on 2010-10-08. Score: 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.


---

### Answer by username_22 on 2010-09-04. Score: 0

[Dynamic Programming](http://en.wikipedia.org/wiki/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).

> **Comments:**
> **username_3**: 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.  

---

