<p><a href="http://en.wikipedia.org/wiki/Pagerank">PageRank</a> is one of the best-known such algorithms. Developed by Google co-founder Larry Page and co-authors, it formed the basis of Google's original search engine and is <a href="http://blog.computationalcomplexity.org/2013/07/altavista-versus-google.html">widely credited</a> with helping them to achieve better search results than their competitors at the time.</p>

<p>We imagine a "random surfer" starting at some webpage, and repeatedly clicking a random link to take him to a new page. The question is, "What fraction of the time will the surfer spend at each page?" The more time the surfer spends at a page, the more important the page is considered.</p>

<p>More formally, we view the internet as a graph where pages are nodes and links are directed edges. We can then model the surfer's action as a random walk on a graph or equivalently as a Markov Chain with transition matrix $M$. After dealing with some issues to ensure that the Markov Chain is ergodic (where does the surfer go if a page has no outgoing links?), we compute the amount of time the surfer spends at each page as the steady state distribution of the Markov Chain.</p>

<p>The algorithm itself is in some sense trivial - we just compute $M^k \pi_0$ for large $k$ and arbitrary initial distribution $\pi_0$. This just amounts to repeated matrix-matrix or matrix-vector multiplication. The algorithms content is mainly in the set-up (ensuring ergodicity, proving that an ergodic Markov Chain has a unique steady state distribution) and convergence analysis (dependence on the spectral gap of $M$).</p>

CC BY-SA 3.0
2013-11-12T18:48:52.323Z
I don't think this is typical algorithms material.
Manu
CC BY-SA 3.0
2013-11-12T19:11:01.887Z
Incidentally I first learned about PageRank in an algorithms class. In fact, I think the professor chose it because it was a nice example of "algorithms used in practice." If you limit examples to "first half of CLRS" type material, the list of examples will either be too long or too trivial -- quicksort, B-trees, and Dijkstra's algorithm are ubiquitous.
Huck Bennett
CC BY-SA 3.0
2013-11-12T20:09:13.143Z
@EmanueleViola I am currently an information science student at a university. I have not taken algorithms but I have had Markov chains and PageRank in other classes
ford prefect
CC BY-SA 3.0
2013-11-13T01:10:50.487Z
We teach PageRank to undergraduates.
Aaron Roth
CC BY-SA 3.0
2013-11-13T06:53:35.370Z
I teach it to undergraduates also (both in the required algorithms class and in a more specialized graph algorithms elective).
David Eppstein
CC BY-SA 3.0
2013-11-13T08:45:18.253Z
I learnt PageRank as an undergraduate in an elective.
Vijay D
CC BY-SA 3.0
2013-11-13T11:19:36.823Z
Alright, PageRank should qualify even though it's not in standard textbooks (I think).  Though the algorithm is a bit atypical (when compared to other core algorithms), because as Huck says it's pretty much all in the analysis.
Manu
CC BY-SA 3.0
2013-12-03T06:17:55.967Z
Isn't pagerank supposed to be based on the number of backlinks from other pages? You say it is based on the time that a user spends on a page; which is data a search engine cannot have.
Anirudh Ramanathan
CC BY-SA 3.0
2013-12-03T15:00:43.050Z
Here "time" means the fraction of steps in the Markov Chain that the user spends at the page.
Huck Bennett
CC BY-SA 3.0
2015-05-11T17:55:37.753Z
You forgot to mention the father of PageRank: the Hub-Authority algorithm. In my opinion, it's a far more commonly studied algorithm, because it's simpler and the subsequent algorithms like PageRank can be easily derived as enhancements.
gaborous
CC BY-SA 3.0
2013-11-12T16:47:22.787Z
2013-11-12T16:47:22.787Z
Huck Bennett
<p>I would mention the widely-used software CPLEX (or similar) implementation of the Simplex method/algorithm 
for solving linear programming problems. 
It is the (?) most used algorithm in economy and operations research. </p>

<p><em>"If one would take statistics about which mathematical
problem is using up most of the computer time in the
world, then (not counting database handling problems
like sorting and searching) the answer would probably be
linear programming.</em>" (L. Lovász, A new linear programming algorithm-better 
or worse than the simplex method? Math. Intelligencer 2 (3) (1979/80) 141-146.) </p>

<p>The Simplex algorithm has also great influence in theory; see, for instance, 
the <a href="https://cstheory.stackexchange.com/questions/1814/a-combinatorial-version-for-the-polynomial-hirsch-conjecture">(Polynomial) Hirsch Conjecture</a>.</p>

<p>I guess a typical undergraduate or Ph.D. class in algorithms deals with the Simplex algorithm 
(including basic algorithms from linear algebra like Gauss Elimination Method).</p>

<p>(Other successful algorithms, including Quicksort for sorting, are listed in 
<a href="https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book">Algorithms from the Book</a>.)</p>

CC BY-SA 3.0
2013-11-12T18:47:58.240Z
"economy and operations research" isn't specific enough.  CPLEX isn't the type of example I was looking for either, as it is just an implementation of the algorithm; it would be different if, say, the gcc compiler used the simplex method.
Manu
CC BY-SA 3.0
2013-11-12T19:12:57.093Z
I think "linear programming problems" is specific enough when we speak about economy and OR. Also, by CPLEX  
I meant the algorithm behind the implementation.
vb le
CC BY-SA 3.0
2013-11-12T19:22:43.753Z
"Today, most large firms use linear programming to price products and manage supply chains. Transportation firms use it to choose the cheapest way to consolidate, coordinate and route shipments of many products from globally distributed suppliers to distant markets subject to capacity constraints. The petroleum industry uses it for exploration, blending, production scheduling and distribution. The iron and steel industry uses it to evaluate iron ores, explore the addition of coke ovens and select products..." http://news.stanford.edu/news/2005/may25/dantzigobit-052505.html
Sasho Nikolov
CC BY-SA 3.0
2013-11-13T11:13:16.720Z
Thanks.  But I find the quote terribly vague.  I think if I say that in front of a class of students, half of it would fall asleep ;-)  It would be different if we say something like: UPS uses LP to ship packages as follows... I am not saying such examples are trivial to find, but given that "most large firms use LP" I'd hope we can at least point to *one*.
Manu
CC BY-SA 3.0
2013-11-13T16:39:53.593Z
Off the top of my head, since 2007 LAX (the airport) has used software for solving Stackelberg games to schedule the security personnel. Solving large LPs is part of the whole thing, see e.g. http://teamcore.usc.edu/ARMOR-LAX/. Besides that, I would ask someone from your Operations Research department: they would usually have plenty of war stories about using LP in real life
Sasho Nikolov
CC BY-SA 3.0
2013-11-12T17:03:29.170Z
2013-11-12T17:03:29.170Z
2017-04-13T12:32:30.623Z
vb le
<p>As I understand it, the <a href="http://en.wikipedia.org/wiki/National_Resident_Matching_Program">National Resident Matching Program</a> was for a long time just a straight application of the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem">Gale-Shapley algorithm</a> for the stable marriage problem. It has since been slightly updated to handle some extra details like spousal assignments (aka the "two-body problem"), etc...</p>

CC BY-SA 3.0
2013-11-12T18:52:08.943Z
I am not sure stable marriage is typical algorithms material.
Manu
CC BY-SA 3.0
2013-11-12T19:11:35.547Z
It's in the Tardos and Kleinberg Algorithms Design book, and also in Motwani's Randomized Algorithms, and both books are widely used. Stable marriage may not be universally taught in algorithms courses, but it certainly is taught in a lot of them.
Sasho Nikolov
CC BY-SA 3.0
2013-11-12T19:18:45.647Z
A quick search reveals that it has shown up in [Berkeley's CS70](http://www.cs.berkeley.edu/~daw/teaching/cs70-s08/notes/n7.pdf), [MIT's 6.042](http://courses.csail.mit.edu/6.042/fall11/slides8w.pdf), [UMD's CMSC451](https://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec01-stable.pdf), etc...
mhum
CC BY-SA 3.0
2013-11-12T21:16:39.503Z
Interestingly, when you add in spousal assignments, the problem becomes NP-complete: http://arxiv.org/abs/1308.4534. However, in practice this seems not to cause too much of a problem: http://en.wikipedia.org/wiki/National_Resident_Matching_Program#Couples
Joshua Grochow
CC BY-SA 3.0
2013-11-12T22:46:51.350Z
@EmanueleViola while it might not be covered traditionally, its inclusion in the Kleinberg/Tardos book has made it more popular, (and if not it should be !)
Suresh Venkat
CC BY-SA 3.0
2013-11-13T11:23:15.400Z
I agree that the inclusion in Kleinberg Tardos' book makes this qualify.
Manu
CC BY-SA 3.0
2013-11-12T18:25:26.900Z
2013-11-12T18:25:26.900Z
mhum
<p>GNU <strong>grep</strong> is a command line tool for searching one or more input files for lines containing a match to a specified pattern. It is well-known that <strong>grep</strong> is very fast! Here's a quote from its author Mike Haertel (taken from <a href="http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html">here</a>):</p>

<pre><code>GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the
final letter of the target string, and uses a lookup table to tell it how far
ahead it can skip in the input whenever it finds a non-matching character.
</code></pre>

CC BY-SA 3.0
2013-11-12T23:06:37.780Z
2013-11-12T23:12:34.367Z
2013-11-12T23:12:34.367Z
Dai Le
<p>More generally, the <a href="http://awards.acm.org/kanellakis/">Kanellakis prize</a> is awarded by the ACM for precisely such theoretical discoveries that have had a major impact in practice. </p>

<p>the 2012 award is for <a href="http://awards.acm.org/press_releases/tech_awards_2012.pdf">locality-sensitive hashing</a>, which has become a go-to method for dimensionality reduction in data mining for near neighbor problems (and is relatively easy to teach - at least the algorithm itself)</p>

CC BY-SA 3.0
2013-11-12T18:51:16.707Z
I think this is teachable but not widely taught.
Manu
CC BY-SA 3.0
2013-11-12T22:45:13.203Z
Unfortunate, but true. However, variants of LSH (like the Count-min sketch and relatives) are beginning to appear in "large-data" or "data mining" courses. I teach bloom filters in my algorithms class, for example.
Suresh Venkat
CC BY-SA 3.0
2013-11-14T21:45:56.280Z
As a personal experience, LSH did not scale for us on an instance of a "big data" (100mln items).
lynxoid
CC BY-SA 3.0
2013-11-14T22:04:53.263Z
@lynxoid that's a separate discussion/question :). There are enough examples of where it *does* work that I think it's relevant to this particular question.
Suresh Venkat
CC BY-SA 3.0
2013-11-12T17:26:27.400Z
2013-11-12T17:26:27.400Z
Suresh Venkat
<p>The <a href="http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf">CountMin Sketch</a> and <a href="http://www.mathcs.emory.edu/~cheung/papers/StreamDB/Frequency-count/FrequentStream.pdf">Count Sketch</a>, from data streaming algorithms, are used in industrial systems for network traffic analysis and analysis of very large unstructured data. These are data structure that summarize the frequency of a huge number of items in a tiny amount of space. Of course they do that approximately, and the guarantee is that, with high probability, the frequency of any item is approximated to within an an $\varepsilon$-fraction of the total "mass" of all items (the mass is the first or second moment of the frequency vector). This is good enough to find "trending" items, which is what you need in a lot of applications.</p>

<p>Some examples of industrial uses of these data structures are:</p>

<ul>
<li>Google's <a href="http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/sawzall-sciprog.pdf">Sawzall</a> system for unstructured data analysis uses the Count Sketch to implement a 'most popular items' function</li>
<li>AT&amp;T's <a href="http://www2.research.att.com/~divesh/meetings/mpds2003/schedule/spatscheck.pdf">Gigascope</a> "stream database" system for network traffic monitoring <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.2012&amp;rep=rep1&amp;type=pdf">implements</a> the CountMin sketch.</li>
<li>Sprint's Continous Monitoring (CMON) system <a href="http://www.cs.rutgers.edu/~muthu/ss.pdf">implements</a> CountMin.</li>
</ul>

<p>Here is also a <a href="https://sites.google.com/site/countminsketch/home">site</a> that collects information about applications of CountMin.</p>

<p>As far as teaching, I know that basic sketching techniques are taught at Princeton in undergraduate discrete math courses. I was taught the CountMin sketch in my first algorithms course. In any case, the analysis of CountMin is simpler than the analysis for almost any other randomized algorithm: it's a straightforward application of pairwise independence and Markov's inequality. If this is not standard material in most algorithms courses, I think it's for historical reasons.</p>

CC BY-SA 3.0
2013-11-13T11:31:51.433Z
Great examples (though not quite core algo right now).
Manu
CC BY-SA 3.0
2013-11-12T19:05:27.177Z
2013-11-12T19:05:27.177Z
Sasho Nikolov
<p>In the last decade algorithms have been used to increase the number (and quality, I think?) of kidney transplants through various kidney donor matching programs. I've been having trouble finding the latest news on this, but here are at least a few pointers:</p>

<ul>
<li><p>As recently as 2007 the Alliance for Paired Donation was using an algorithm of <a href="http://www.cs.cmu.edu/~avrim/Papers/ec150abraham.pdf">Abraham, Blum, and Sandholm</a>. They may still be using it, but I couldn't find out by searching online. Although this algorithm is almost surely not covered in "standard" courses, it combines several fundamental ideas that surely are taught in such courses to provide a good enough algorithm for a problem that is, in general, NP-complete (a variant of Cycle Cover).</p></li>
<li><p>The National Kidney Registry also uses some standard algorithms, including (at one point) CPLEX. This led to an actually performed <a href="http://www.nytimes.com/2012/02/19/health/lives-forever-linked-through-kidney-transplant-chain-124.html?pagewanted=all&amp;_r=0">chain of transplants linking 60 people</a>.</p></li>
</ul>

<p>This is one of my favorite examples not just of the success of algorithms, but of the importance of studying algorithms for NP-complete problems. They can <em>literally save lives</em>, and have already done so!</p>

CC BY-SA 3.0
2013-11-19T21:49:05.410Z
Also, a simpler version of these algorithms is used to trade board games: http://okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html
Radu GRIGore
CC BY-SA 3.0
2013-11-13T20:08:12.367Z
2013-11-13T20:08:12.367Z
Joshua Grochow
<p>Viterbi's algorithm, which is still widely used in speech recognition and multiple other applications: <a href="http://en.wikipedia.org/wiki/Viterbi_algorithm">http://en.wikipedia.org/wiki/Viterbi_algorithm</a> The algorithm itself is basic dynamic programming.</p>

<p>From Wikipedia:
"The Viterbi algorithm was proposed by Andrew Viterbi in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links.[1] The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognition, speech synthesis, keyword spotting, computational linguistics, and bioinformatics. For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal."</p>

CC BY-SA 3.0
2013-11-14T00:00:35.737Z
2013-11-14T00:11:43.060Z
2013-11-14T00:11:43.060Z
Grigory Yaroslavtsev
<p>If you're also including PhD-level stuff, many (most?) graduate CS programs include some course in coding theory. If you have a course in coding theory, you will definitely cover the <a href="http://en.wikipedia.org/wiki/Reed_Solomon">Reed-Solomon code</a> which is integral to how compact discs work and <a href="http://en.wikipedia.org/wiki/Huffman_encoding">Huffman encoding</a> which is used in JPEG, MP3, and ZIP file formats. Depending on the orientation of the course, you may also cover <a href="http://en.wikipedia.org/wiki/Lempel_Ziv">Lempel-Ziv</a> which is used in the GIF format. Personally, I got Lempel-Ziv in an undergraduate algorithms course, but I think that might be atypical.</p>

CC BY-SA 3.0
2013-11-12T22:59:26.657Z
And I got a lecture on Huffman encoding as an undergrad, which was required for a project.
Brian S
CC BY-SA 3.0
2013-11-14T14:42:51.560Z
Huffman is in one of the first chapters of CLRS, so it should definitely qualify
Sasho Nikolov
CC BY-SA 3.0
2013-11-12T22:25:44.210Z
2013-11-12T22:25:44.210Z
mhum
<ol>
<li>A* is used in many Personal Navigation Devices (aka GPS units)</li>
<li>A* is very well defined, and has been implemented fairly straightforward.</li>
<li>A* isn't entirely trivial, but it doesn't take a Ph.D. to understand it.</li>
</ol>

CC BY-SA 3.0
2013-11-12T22:57:57.277Z
A* is also frequently taught in game design. I don't _think_ modern 3D games generally use A* for NPC navigation, but 2D/isometric games, as well as older games, do make use of the algorithm.
Brian S
CC BY-SA 3.0
2013-11-13T17:24:58.563Z
@BrianS Do you know examples of pathfinding algorithms used in 3D games, specifically enemies NPCs in games (such as a shooter npc) I remember reading something like... dividing a map in hexagonal sectors and use that as the node, instead of squares, and that allowed a smoother movement.
Goodwine
CC BY-SA 3.0
2013-11-13T22:35:51.333Z
@Goodwine, Sorry, I do not have any real-world examples of pathfinding algorithms in 3D games. My personal experience has been with "cube"-like environments (map made of cubes, which characters stand on -- basically 2D, despite 3D rendering) and dummy AIs used for testing player-characters against.
Brian S
CC BY-SA 3.0
2013-11-12T20:33:40.133Z
2013-11-12T20:33:40.133Z
MSalters
<p>Check out Jens Vygen's project BonnTools for Chip Design.
<a href="http://www.or.uni-bonn.de/~vygen/projects.html">http://www.or.uni-bonn.de/~vygen/projects.html</a>
I have heard some talks on this and also looked at some of their papers.
They use Raghavan-Thompson style randomized rounding as well as multiplicative weight update method for solving large-scale multicommodity flow LPs. 
However, like any big project, they need to do some engineering as well but the methodology is very much based on well-known algorithms.</p>

CC BY-SA 3.0
2013-11-12T18:50:02.013Z
I'll have a look but it doesn't sound like typical algorithms material.
Manu
CC BY-SA 3.0
2013-11-12T20:44:45.267Z
Hmm, randomized rounding is typically taught in PhD level algorithms courses, no?
Chandra Chekuri
CC BY-SA 3.0
2013-11-14T06:07:31.457Z
Why just randomized rounding? Sanjeev Arora, Elad Hazan and Satyen Kale think that even mulplicative weights update method is basic enough to be taught at UG level :) "We feel that our meta algorithm and its analysis are simple and useful enough that they should be viewed as a basic tool taught to all algorithms students together with divide-and-conquer, dynamic programming, random sampling, and the like."  (cf. http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf).
Jagadish
CC BY-SA 3.0
2013-11-12T15:56:23.097Z
2013-11-12T15:56:23.097Z
Chandra Chekuri
<p>Funny that I saw this question today and then coincidentally clicked <a href="http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-homer-simpsons-face">this link on the many uses of the Fourier Transform</a>.</p>

CC BY-SA 3.0
2013-11-13T08:21:11.147Z
2013-11-13T08:21:11.147Z
John Wu
<p>I like this system for saving the maximum number of lives in the UK with kidney transplants, based on maximum matching algorithms: <a href="http://link.springer.com/chapter/10.1007/978-3-642-30850-5_24">Paired and Altruistic Kidney Donation</a>. 
They match up people needing kidneys who have a non-matching friend/relative willing to donate, with other people in the same situation, in a maximal way. Then on donation day, all the donors donate at the same time, followed by a speedy transport of kidneys around the country to the recipients. </p>

CC BY-SA 3.0
2013-11-13T10:54:38.303Z
2013-11-13T10:54:38.303Z
Alnitak
<p>I'm rather surprised that with all the fancy algorithms above, nobody mentioned the venerable Lempel-Ziv family of compression algorithms (invented in 1977/78).</p>

<ol>
<li>Those are used everywhere - text to image to stream processing. It is quite possible that LZ* is a single most used algorithm family in existence.</li>
<li>Dictionary compression was a considerable breakthrough in compression theory and a stark departure from Shannon-Fano style approach.</li>
<li>The algorithms in the family are rather straightforward and easy to comprehend.</li>
</ol>

<p><strong>Update</strong></p>

<p>Apparently it was mentioned briefly already.</p>

CC BY-SA 3.0
2013-11-13T00:19:02.653Z
2013-11-13T00:19:02.653Z
oakad
<p><a href="http://en.wikipedia.org/wiki/Singular_value_decomposition">singular value decomposition</a> (SVD) has a strong connection to statistical <a href="http://en.wikipedia.org/wiki/Factor_analysis">factor analysis</a> or <a href="http://en.wikipedia.org/wiki/Principal_components_analysis">principal components analysis</a> and is comprehensible within an undergraduate linear algebra or statistics class, and has many important theoretical properties. it also plays a role in image compression algorithms. it played a key element in the winning entries in the <a href="http://en.wikipedia.org/wiki/Netflix_prize">$1M Netflix prize contest</a> (one of the worlds largest datamining competitions in history) and is now implemented on their site to predict user ratings. it is also known to be highly related to <a href="http://en.wikipedia.org/wiki/Hebbian_learning">Hebbian self-organizing neural networks</a> which originate in biological theory. </p>

<p>there is some connection also to <a href="http://en.wikipedia.org/wiki/Gradient_descent">gradient descent</a> which is used widely in <a href="http://en.wikipedia.org/wiki/Machine_learning">machine learning</a> &amp; <a href="http://en.wikipedia.org/wiki/Artificial_neural_networks">artificial neural networks</a> and as a very universally applied optimization technique of which case <a href="http://en.wikipedia.org/wiki/Newtons_method">Newton's method</a> is a basic 2d form. there is a gradient-descent algorithm for obtaining the SVD.</p>

CC BY-SA 3.0
2013-11-13T01:59:46.993Z
2013-11-13T01:59:46.993Z
vzn
<p>Finding a Eulerian path is at the base of the genome assembly -- a task commonly performed when working with full genomes (in bioinformatics, medicine, forensics, ecology).</p>

<p><strong>UPDATE</strong> Forgot this obvious one: UPS, FedEx, USPS all have to solve large instances of Traveling Salesman Problem every night. Saves a lot of time and money for them to send the drivers on an optimal route.</p>

<p><strong>UPDATE2</strong> Minimum feedback vertex set problem is used for deadlock resolution in many OSes.</p>

CC BY-SA 3.0
2013-11-13T17:28:32.743Z
Are you sure TSP is the problem that the parcel delivery companies are trying to solve?  I thought a bigger practical challenge was knapsack and other kinds of packing problems.
András Salamon
CC BY-SA 3.0
2013-11-14T21:40:51.003Z
The assignments for the drivers change every day (i.e. UPS guy doesn't need to visit the same house every day), so the routes have to be updated on a daily basis. It is not a pure TSP - there are additional constraints such as one-way streets, no U-turns, delivering packages on one side of the street, but not the other.
lynxoid
CC BY-SA 3.0
2013-11-14T21:42:11.463Z
I'm sure packing is also important though.
lynxoid
CC BY-SA 3.0
2013-11-12T23:54:09.460Z
2013-11-13T17:11:45.123Z
2013-11-13T17:11:45.123Z
lynxoid
<p>this relatively new book is worth considering as a complete/detailed answer to the question in convenient, extended/collected form and which could be used as supplemental material for an algorithms class. [some of these have already been mentioned; the strong overlap itself is notable.]</p>

<ul>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/0691158193">Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers</a> by MacCormick</p>

<ul>
<li>search engine indexing</li>
<li>Pagerank</li>
<li>public key cryptography</li>
<li>error correcting codes</li>
<li>pattern recognition</li>
<li>data compression</li>
<li>databases</li>
<li>digital signatures</li>
<li>computability theory</li>
</ul></li>
<li><p>another reference somewhat similar but more theoretical, <a href="http://www.siam.org/pdf/news/637.pdf">The Best of the 20th Century: Editors Name Top 10 Algorithms</a> Cipra/SIAM.</p>

<ul>
<li>Monte Carlo method</li>
<li>simplex algorithm</li>
<li>Krylov subspace iteration</li>
<li>decompositional matrix computation</li>
<li>Fortran compiler</li>
<li>QR matrix algorithm</li>
<li>quicksort</li>
<li>FFT</li>
<li>integer relation detection</li>
<li>fast multipole algorithm</li>
</ul></li>
</ul>

CC BY-SA 3.0
2013-11-14T15:58:59.147Z
2nd ref is originally from January/February 2000 issue of Computing in Science & Engineering, a joint publication of the American Institute of Physics and the IEEE Computer Society. compiled by guest editors Jack Dongarra of the
University of Tennessee and Oak Ridge National Laboratory and Francis Sullivan of the Center for Computing Sciences at the Institute for
Defense Analyses
vzn
CC BY-SA 3.0
2013-11-14T02:19:03.407Z
2013-11-14T02:19:03.407Z
vzn
<p>Thinking of very basic algorithms</p>

<ol>
<li>Random number generators are found everywhere and specifically in all games.</li>
<li>Databases are composed of many algorithms, including B+, Hashes, priority queues, regular expression, criptography, sorting, etc... A friend of mine says SGBDs are at the top of the computing food chain.</li>
<li>Sort is used everywhere, for example in Excel. It is actually used all time in real life, but usually humans use ad-hoc algorithms</li>
<li>Parity bits are used all around</li>
<li>Huffman encoding is in compression and transmission software</li>
<li>Stacks (LIFO) are used everywhere. Inside programming languages, in CPUs, etc...</li>
</ol>

<p>Nice to show they appearing in real life:</p>

<p>A. Many groups use a kind of covering tree algorithm to communicate, by dividing telephone lists in hierarchical way among people
B. Cars in a intersection usually use a round-robin algorithm (in a voluntary way)
C. Most places, as banks and hospital, organize their clientes in a FIFO algorithm</p>

CC BY-SA 3.0
2013-11-14T22:22:35.050Z
Sorting isn't an algorithm. It's a task, i.e., something you wish to perform, for which you must design (or, in practice, choose) an algorithm.
David Richerby
CC BY-SA 3.0
2013-11-15T16:29:20.620Z
These don't seem to be specific examples as requested in the question.
Kaveh
CC BY-SA 3.0
2013-11-24T17:30:01.087Z
[SGBD == RDBMS](http://stackoverflow.com/questions/980813/what-does-sgbd-mean) FYI for those didn't know.
Autodidact
CC BY-SA 3.0
2013-11-14T10:12:19.840Z
2013-11-14T10:12:19.840Z
user19461
<p>A fascinating algorithmic problem arises in medical application of CT scan. In Computed Tomography (CT), the body is exposed to X-rays from different angles. At one end of the scanner are the X-ray transmitters and at the other end the sensors. From such a series of scans, an image is reconstructed for the physician to examine! </p>

<p>The <a href="http://shaidekel.tripod.com/Lesson3.pdf" rel="noreferrer">filtered back projection</a>
algorithm is the basis for reconstruction of an image from a set of scans. This algorithm is actually a form of an approximation problem in which the "signal" is sampled below Nyquist rate. This algorithm is in use "behind the scenes" at all hospitals and the basic filtered back projection utilizes undergraduate math such as Fourier transforms to achieve the <a href="http://en.wikipedia.org/wiki/Projection-slice_theorem" rel="noreferrer">Fourier Slice Theorem</a>.</p>

CC BY-SA 3.0
2013-11-14T13:39:21.053Z
2013-11-14T13:51:43.790Z
2013-11-14T13:51:43.790Z
Leeor
<p>An example of FFT</p>

<p>I once helped port an FFT algorithm to a different system language.  </p>

<p>The algorithm was being used to determine line breaks in coaxial delivery of cable tv/internet/phone.  Basically a technician would request a signal to be sent to the customer's box, at the same time they would pull up a real-time display of the statistics for the specific customer, such as QoS, dB, ....  The technician could use the data and a graph to determine within a few feet between the house and pole where a partial break existed (or multiple breaks as I was told).  </p>

<p>As mentioned above FFT is widely used, but this was one of the more blatant and obvious (in terms of why and how) I have seen in practice.  </p>

<p>Sorry I had to keep it a high level.  </p>

CC BY-SA 3.0
2013-11-15T15:22:49.840Z
2013-11-16T05:27:31.530Z
2013-11-16T05:27:31.530Z
ClericGunem
<p>The <a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm">Knuth-Morris-Pratt</a> string search is widely used, specific, and taught in undergrad / graduate CS.</p>

CC BY-SA 3.0
2013-11-12T18:50:48.143Z
Would be good if you could point to a specific use.  Something like MS Word uses KMP.
Manu
CC BY-SA 3.0
2013-11-12T18:02:35.010Z
2013-11-12T18:02:35.010Z
Darth Egregious
<p><strong>Customizable Route Planning</strong> (Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck) <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=145688" rel="nofollow">http://research.microsoft.com/apps/pubs/default.aspx?id=145688</a></p>

<p>powers Bing Maps: <a href="http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx" rel="nofollow">http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx</a></p>

CC BY-SA 3.0
2013-11-24T04:15:23.657Z
2013-11-24T04:15:23.657Z
Christian Sommer
<p>Bresenham's line algorithm is the single most useful algorithm I've come across. Easy to understand Ive used it for lots of applications from line drawing to a complex spliner for 3d casting engine to a complex polygon renderer, as well as for complex animation and scaling uses.</p>

CC BY-SA 3.0
2013-11-13T09:58:05.250Z
2013-11-13T09:58:05.250Z
TimRing
<p>Wikipedia has a decent collection of algorithms/applications classified more or less in a <a href="http://en.wikipedia.org/wiki/List_of_important_publications_in_computer_science" rel="nofollow">list</a>.
Microsoft provides the <a href="http://academic.research.microsoft.com/RankList?entitytype=1&amp;topDomainID=2&amp;subDomainID=0&amp;last=0&amp;start=1&amp;end=100" rel="nofollow">top cited papers</a> but without any explicit explanation of the area of computer science nor the application. There is also a chronological list from different CS conferences _http://jeffhuang.com/best_paper_awards.html_ compiled by Prof. Huang.</p>

<p><em>Spectral Clustering</em> is an elegant clustering algorithm,  known being <em>Normalized cuts</em> algorithm introduced by Jianbo Shi and Jitendra Malik for image segmentation. It has also well been developed in Data clustering applications, being an good intersection between the two communities.</p>

CC BY-SA 3.0
2013-11-13T16:27:19.973Z
2013-11-13T16:27:19.973Z
Ravi Kiran
<p>two other personal favorite examples firmly rooted in computer science but maybe easily overlooked by abstractionist theoreticians, which have undergone enormous/transformative advances and had major-to-massive practical/applied impact in daily life over the last few decades. already an entire generation has grown up not knowing the world without them. basically the category of <a href="http://en.wikipedia.org/wiki/Modeling_and_simulation" rel="nofollow">Modelling and simulation</a>.</p>

<ul>
<li><p><a href="http://en.wikipedia.org/wiki/Dynamical_simulation" rel="nofollow">physics simulation algorithms</a>. mainly using Newtons laws but using other laws (such as fluid dynamics). used in a wide variety of applications ranging from engineering applications, video games, and sometimes movies. this is responsible also for significantly improving safety, efficiency, or reliability of eg cars &amp; airplanes via subjecting virtual/test designs to simulated stresses. a major related ongoing research area from bioinformatics with massive implications in biology eg drug design, disease prevention etc: <a href="http://en.wikipedia.org/wiki/Protein_structure_prediction" rel="nofollow">protein folding/structure prediction</a>. also note this years Nobel Prize in Chemistry was awarded for <a href="http://www.nytimes.com/2013/10/10/science/three-researchers-win-nobel-prize-in-chemistry.html" rel="nofollow">chemistry simulation</a> to Karplus, Levitt, Warshel. physics simulation algorithms are highly involved in <a href="http://www.state.gov/t/avc/rls/202014.htm" rel="nofollow">nuclear weapons safety/testing</a> eg at Los Alamos laboratories.</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Raytracing" rel="nofollow">raytracing/CGI algorithms</a>. this started out as a research topic merely a few decades ago [a friend got his masters degree in CS writing raytracing algorithms] but became very applied in eg games and the movie making business, reaching extraordinary levels of verisimilitude that is responsible for large amounts of special effects in movies. these industries have literally <em>billions of dollars</em> invested and riding on these algorithms and entire large corporations are based on harnessing them, eg <a href="http://en.wikipedia.org/wiki/Pixar" rel="nofollow">Pixar</a>. mostly initially used in eg scifi movies, the technique is now so widespread it is routinely used even in "typical" movies. for example recently <a href="http://www.imdb.com/title/tt1343092/?ref_=nv_sr_1" rel="nofollow">The Great Gatsby</a> relied heavily on CGI effects to draw convincing or stylized environments, retouch the film/characters, etc.</p></li>
</ul>

CC BY-SA 3.0
2013-11-14T23:37:51.577Z
2013-11-14T23:43:28.633Z
2013-11-14T23:43:28.633Z
vzn
<p>Rosetta Code lists applied algorithms by <a href="http://rosettacode.org/wiki/Category%3aProgramming_Tasks" rel="nofollow">Programming Task</a> (692) and by <a href="http://rosettacode.org/wiki/Category%3aProgramming_Languages" rel="nofollow">Programming Language</a> (518) with Semantic MediaWiki.</p>

CC BY-SA 3.0
2013-11-25T16:34:19.830Z
How is this an example of "core algorithms... deployed in commercial, governmental, or widely-used software/hardware"?
David Richerby
CC BY-SA 3.0
2013-11-26T10:46:49.440Z
It would be useful to cross-reference the implementations of each of the excellent algorithms listed in other answers here to Wikipedia/DBpedia URIs. There aren't Wikipedia/DBpedia URIs for all of these algorithms; but there are Rosetta Code pages.
Wes Turner
CC BY-SA 3.0
2013-11-26T10:48:35.150Z
http://bigocheatsheet.com/ also lists Big-O complexity and links to Wikipedia articles for quite a few algorithms.
Wes Turner
CC BY-SA 3.0
2013-11-26T13:32:35.487Z
The question asks for examples of core algorithms used in significant pieces of software.  "Here's a website with algorithms implemented in a million languages" doesn't answer that question at all. In fact, it's the exact opposite of what the question is looking for.
David Richerby
CC BY-SA 3.0
2013-11-27T00:36:59.913Z
A useful, contextually relevant reference nonetheless.
Wes Turner
CC BY-SA 3.0
2013-11-24T07:42:00.040Z
2013-11-24T07:42:00.040Z
Wes Turner
<p>maybe all the major/preferred algorithms of interest to this audience have been mentioned at this point. however, a few more deserve mention for completeness. &amp; some analysis of what is considered a significant algorithm is relevant here.</p>

<p>in CS &amp; IT fields there seems to be a phenomenon noticed long ago in AI called <a href="http://en.wikipedia.org/wiki/Moving_the_goalpost" rel="nofollow">"moving the goalposts"</a>. this is a psychological phenomenon where the field advances relatively quickly but people quickly mentally adjust to "the new normal" and take real or even breakthrough advances as mundane or unremarkable in retrospect, after accomplished, ie downplayed or minimized. this is highly captured in this question in the way that algorithms move from R&amp;D into "deployment". quoting the author of the question in later comments:</p>

<blockquote>
  <p>In fact, a negligible fraction of all the code that gets written is implementing anything that is interesting from an algorithmic point of view.</p>
</blockquote>

<p>but this is problematic and basically a TCS-centric redefinition of the word "algorithm". presumably the interesting algorithms are advanced. does that mean that if a problem is reduced to an advanced algorithm, its no longer "interesting"? and "advanced" is clearly a moving target. so there is a way to define "algorithms" <em>narrowly</em>, or <em>broadly</em>. it seems the TCS definition changes on context, but note even in TCS, there is a trend toward the <em>broad</em> definition eg in the so-called <a href="http://lazowska.cs.washington.edu/fcrc/Christos.FCRC.pdf" rel="nofollow">"algorithmic lens"</a>.</p>

<p>sometimes the most ubiquitous algorithms are also the most overlooked! the internet and WWW is a large environment/near-ecology for algorithms. still relatively young at only about 2 decades old (invented ~1991) it has grown massively and exponentially in a short amount of time. WWW site growth has probably even outpaced the famous exponential Moores law.</p>

<p>the internet/WWW are supported by many sophisticated algorithms. the internet has complex routing algorithms built into routers (again powering multi-billion-dollar corporations such as Cisco). some advanced theory is applicable there eg in <a href="http://en.wikipedia.org/wiki/Routing" rel="nofollow">routing algorithms</a>. these algorithms were a subject of emerging, advanced/cutting edge research decades ago however a now so finetuned &amp; well understood that its somewhat invisible. </p>

<p>we should not so soon forget that decades ago, leading researchers were not even sure if the internet world work or was possible (seen in early packet switching research, a radical new design pattern at the time departing from the prior circuit-switching), and even a few years ago there were fears that it would fail to scale at some point and begin to fail due to overwhelming spikes in volume.</p>

<p>it also uses sophisticated <a href="http://en.wikipedia.org/wiki/Error_correction" rel="nofollow">error detection/correction</a>. the internet probably <em>the</em> largest, most <a href="http://en.wikipedia.org/wiki/Fault_tolerance" rel="nofollow">fault-tolerant</a> system ever built by humans, still growing.</p>

<p>next, there is a strong case to make that the algorithms powering the WWW are advanced. <a href="http://en.wikipedia.org/wiki/Http" rel="nofollow">HTTP</a> &amp; web servers are highly tuned/optimized and also use advanced security/encryption protocols (HTTPS). the rendering logic of a web page has become extremely advanced in <a href="http://en.wikipedia.org/wiki/Html5" rel="nofollow">HTML5</a> &amp; <a href="http://en.wikipedia.org/wiki/Css" rel="nofollow">CSS3</a>, along with the <a href="http://en.wikipedia.org/wiki/Javascript" rel="nofollow">Javascript</a> programming language. </p>

<p>the relatively new CSS has various principles similar to <a href="http://en.wikipedia.org/wiki/Object_oriented_programming" rel="nofollow">OOP programming</a> such as reusability and inheritance. speaking of typesetting, <a href="http://en.wikipedia.org/wiki/TeX" rel="nofollow">TeX</a> is an important, internally complex scientific typesetting system (not so different than a programming language) invented by Knuth that can now be rendered on web pages (and is used in possibly hundreds of thousands of scientific papers or more).</p>

<p>another relatively new area of algorithms building on the internet, still emerging, those based on <a href="http://en.wikipedia.org/wiki/Collective_intelligence" rel="nofollow">collective intelligence</a>. stackexchange software itself is an example of a sophisticated collective intelligence system. <a href="http://en.wikipedia.org/wiki/Social_networking" rel="nofollow">social networking</a> also exhibits the key features of collective intelligence and features are continually being added to increase that intelligence (for example facebook "Likes" are only a few years old). the field of rating systems is based on <a href="http://en.wikipedia.org/wiki/Collaborative_filtering" rel="nofollow">collaborative filtering</a> algorithms and is still evolving based on new research and applications.</p>

<p>so in short, all <em>revolutionary successes transforming daily human experience</em> actually quite far beyond merely "field goals". as the title of the question states, all <em>core algorithms deployed</em>. now so ubiquitous and invisible as to be something like the IT expression, "part of the plumbing".</p>

CC BY-SA 3.0
2013-11-19T18:32:17.457Z
many citations could be added to this. here is one to start: [DARPA and the internet revolution](http://www.darpa.mil/WorkArea/DownloadAsset.aspx@id=2554.pdf) by Waldrop
vzn
CC BY-SA 3.0
2013-12-01T03:40:04.767Z
another ref on internet optimization, [biography of Danny Lewin](http://en.wikipedia.org/wiki/Citation_analysis), cofounder of akamai, "the genius who transformed the internet"
vzn
CC BY-SA 3.0
2013-11-16T16:46:01.683Z
2013-11-16T16:46:01.683Z
vzn
<p>An amazingly successful (hardware) algorithm is the power-on reset.</p>

<p>Without a system whereby a computer is in a known state when power is applied, <strong>nothing else happens right</strong>.</p>

<p>Power-on reset is why anything works at all that has a CPU in it, whether considered embedded or otherwise.</p>

<p>Next time you're at the watering hole for programmers and computer scientists, raise your glass of cherry soda to the power-on reset.</p>

CC BY-SA 3.0
2013-11-14T22:21:37.953Z
Power-on reset isn't an algorithm. It's a task, i.e., something you wish to perform, for which you must design an algorithm.
David Richerby
CC BY-SA 3.0
2013-11-13T16:40:21.737Z
2013-11-13T16:40:21.737Z
Anon
<p>Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashionable algorithms course material such as Strassen's multiplication, the AKS primality test, or the Moser-Tardos algorithm is relevant for low-level practical problems of implementing a video database, an optimizing compiler, an operating system, a network congestion control system or any other system. The value of these courses is learning that there are intricate ways to exploit the structure of a problem to find efficient solutions. Advanced algorithms is also where one meets simple algorithms whose analysis is non-trivial. For this reason, I would not dismiss simple randomized algorithms or PageRank.</p>

<p>I think you can choose any large piece of software and find basic and advanced algorithms implemented in it. As a case study, I've done this for the Linux kernel, and shown a few examples from Chromium.</p>

<h2>Basic Data Structures and Algorithms in the Linux kernel</h2>

<p>Links are to the <a href="https://github.com/mirrors/linux-2.6">source code on github</a>.</p>

<ol>
<li><a href="https://github.com/mirrors/linux-2.6/blob/master/lib/llist.c">Linked list</a>, <a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/list.h">doubly linked list</a>, <a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/llist.h">lock-free linked list</a>.</li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/39caa0916ef27cf1da5026eb708a2b8413156f75/lib/btree.c">B+ Trees</a> with comments telling you what you can't find in the textbooks.</p>

<blockquote>
  <p>A relatively simple B+Tree implementation.  I have written it as a learning exercise to understand how B+Trees work.  Turned out to be useful as well.</p>
  
  <p>...</p>
  
  <p>A tricks was used that is not commonly found in textbooks.  The lowest values are to the right, not to the left.  All used slots within a node are on the left, all unused slots contain NUL values.  Most operations simply loop once over all slots and terminate on the first NUL.</p>
</blockquote></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/plist.h">Priority sorted lists</a> used for <a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/rtmutex.h">mutexes</a>, <a href="https://github.com/mirrors/linux-2.6/blob/f0d55cc1a65852e6647d4f5d707c1c9b5471ce3c/drivers/powercap/intel_rapl.c">drivers</a>, etc.</p></li>
<li><a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/rbtree.h">Red-Black trees</a> are <a href="http://lwn.net/Articles/184495/">used</a> for scheduling, virtual memory management, to track file descriptors and directory entries,etc.</li>
<li><a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/interval_tree.h">Interval trees</a></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/radix-tree.h">Radix trees</a>, are used for <a href="http://lwn.net/Articles/175432/">memory management</a>, NFS related lookups and networking related functionality.</p>

<blockquote>
  <p>A common use of the radix tree is to store pointers to struct pages;</p>
</blockquote></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/prio_heap.h">Priority heap</a>, which is literally, a textbook implementation, used in the <a href="https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/include/linux/cgroup.h">control group system</a>.</p>

<blockquote>
  <p>Simple insertion-only static-sized priority heap containing pointers, based on CLR, chapter 7</p>
</blockquote></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/hash.h">Hash functions</a>, with a reference to Knuth and to a paper.</p>

<blockquote>
  <p>Knuth recommends primes in approximately golden ratio to the maximum
  integer representable by a machine word for multiplicative hashing.
  Chuck Lever verified the effectiveness of this technique:</p>
  
  <p><a href="http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf">http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf</a></p>
  
  <p>These primes are chosen to be bit-sparse, that is operations on
  them can use shifts and additions instead of multiplications for
  machines where multiplications are slow.</p>
</blockquote></li>
<li><p>Some parts of the code, such as <a href="https://github.com/mirrors/linux-2.6/blob/0b1e73ed225d8f7aeef96b74147215ca8b990dce/drivers/staging/lustre/lustre/lov/lov_pool.c">this driver</a>, implement their own hash function.</p>

<blockquote>
  <p>hash function using a Rotating Hash algorithm</p>
  
  <p>Knuth, D. The Art of Computer Programming,
  Volume 3: Sorting and Searching,
  Chapter 6.4.
  Addison Wesley, 1973</p>
</blockquote></li>
<li><a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/hashtable.h">Hash tables</a> used to implement <a href="https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/inode.c">inodes</a>, <a href="https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/check-integrity.c">file system integrity checks</a> etc.</li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/bitmap.h">Bit arrays</a>, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4. </p></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/semaphore.h">Semaphores</a> and <a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/spinlock.h">spin locks</a></p></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/master/lib/bsearch.c">Binary search</a> is used for <a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/drivers/sh/intc/chip.c">interrupt handling</a>, <a href="https://github.com/mirrors/linux-2.6/blob/10d0c9705e80bbd3d587c5fad24599aabaca6688/drivers/base/regmap/regcache.c">register cache lookup</a>, etc.</p></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/befs/btree.c">Binary search with B-trees</a></p></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/a9238741987386bb549d61572973c7e62b2a4145/drivers/acpi/acpica/nswalk.c">Depth first search</a> and variant used in <a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/configfs/dir.c">directory configuration</a>.</p>

<blockquote>
  <p>Performs a modified depth-first walk of the namespace tree, starting
  (and ending) at the node specified by start_handle.  The callback
  function is called whenever a node that matches the type parameter is
  found. If the callback function returns a non-zero value, the search
  is terminated immediately and this value is returned to the caller.</p>
</blockquote></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/4fbf888accb39af423f271111d44e8186f053723/kernel/locking/lockdep.c">Breadth first search</a> is used to check correctness of locking at runtime.</p></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/master/lib/list_sort.c">Merge sort</a> on linked lists is used for <a href="https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/ubifs/gc.c">garbage collection</a>, <a href="https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/raid56.c">file system management</a>, etc.</p></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/drivers/media/common/saa7146/saa7146_hlp.c">Bubble sort</a> is amazingly implemented too, in a driver library.</p></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_kmp.c">Knuth-Morris-Pratt string matching</a>, </p>

<blockquote>
  <p>Implements a linear-time string-matching algorithm due to Knuth,
  Morris, and Pratt [1]. Their algorithm avoids the explicit
  computation of the transition function DELTA altogether. Its
  matching time is O(n), for n being length(text), using just an
  auxiliary function PI[1..m], for m being length(pattern),
  precomputed from the pattern in time O(m). The array PI allows
  the transition function DELTA to be computed efficiently
  "on the fly" as needed. Roughly speaking, for any state
  "q" = 0,1,...,m and any character "a" in SIGMA, the value
  PI["q"] contains the information that is independent of "a" and
  is needed to compute DELTA("q", "a") <a href="https://github.com/mirrors/linux-2.6/blob/master/lib/llist.c">2</a>. Since the array PI
  has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
  save a factor of |SIGMA| in the preprocessing time by computing
  PI rather than DELTA.</p>
  
  <p>[1] Cormen, Leiserson, Rivest, Stein
   Introdcution to Algorithms, 2nd Edition, MIT Press</p>
  
  <p>[2] See finite automation theory</p>
</blockquote></li>
<li><p><a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_bm.c">Boyer-Moore pattern matching</a> with references and recommendations for when to prefer the alternative.</p>

<blockquote>
  <p>Implements Boyer-Moore string matching algorithm:</p>
  
  <p>[1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
   Communications of the Association for Computing Machinery, 
   20(10), 1977, pp. 762-772.
   <a href="http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf">http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf</a></p>
  
  <p>[2] Handbook of Exact String Matching Algorithms, Thierry Lecroq,
  2004
   <a href="http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf">http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf</a></p>
  
  <p>Note: Since Boyer-Moore (BM) performs searches for matchings from
  right 
  to left, it's still possible that a matching could be spread over 
  multiple blocks, in that case this algorithm won't find any 
  coincidence.</p>
  
  <p>If you're willing to ensure that such thing won't ever happen,
  use the 
  Knuth-Pratt-Morris (KMP) implementation instead. In conclusion,
  choose 
  the proper string search algorithm depending on your setting. </p>
  
  <p>Say you're using the textsearch infrastructure for filtering,
  NIDS or<br>
  any similar security focused purpose, then go KMP. Otherwise, if
  you 
  really care about performance, say you're classifying packets to
  apply
  Quality of Service (QoS) policies, and you don't mind about
  possible
  matchings spread over multiple fragments, then go BM. </p>
</blockquote></li>
</ol>

<h2>Data Structures and Algorithms in the Chromium Web Browser</h2>

<p>Links are to the <a href="https://code.google.com/p/chromium/">source code on Google code</a>. I'm only going to list a few. I would suggest using the search feature to look up your favourite algorithm or data structure.</p>

<p><ol>
<li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/splay-tree.h">Splay trees</a>.</p>

<blockquote>
  <p>The tree is also parameterized by an allocation policy
  (Allocator). The policy is used for allocating lists in the C free
  store or the zone; see zone.h.</li>
  <li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/native_client_sdk/src/examples/demo/voronoi/index.html">Voronoi diagrams</a> are used in a demo.</li>
  <li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/chrome/browser/ui/cocoa/tabs/tab_strip_controller.mm">Tabbing based on Bresenham's algorithm</a>.</li>
  </ol>
  There are also such data structures and algorithms in the third-party code included in the Chromium code.</p>
</blockquote>

<p><ol>
<li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/bintree.py">Binary trees</a></li>
<li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/rbtree.py">Red-Black trees</a></p>

<blockquote>
  <p>Conclusion of Julian Walker</p>
  
  <p>Red black trees are interesting beasts. They're believed to be
  simpler than
  AVL trees (their direct competitor), and at first glance this seems
  to be the
  case because insertion is a breeze. However, when one begins to play
  with the
  deletion algorithm, red black trees become very tricky. However, the
  counterweight to this added complexity is that both insertion and
  deletion
  can be implemented using a single pass, top-down algorithm. Such is
  not the
  case with AVL trees, where only the insertion algorithm can be
  written top-down.
  Deletion from an AVL tree requires a bottom-up algorithm.</p>
  
  <p>...</p>
  
  <p>Red black trees are popular, as most data structures with a
  whimsical name.
  For example, in Java and C++, the library map structures are
  typically
  implemented with a red black tree. Red black trees are also
  comparable in
  speed to AVL trees. While the balance is not quite as good, the work
  it takes
  to maintain balance is usually better in a red black tree. There are
  a few
  misconceptions floating around, but for the most part the hype about
  red black
  trees is accurate.</li>
  <li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/avltree.py">AVL trees</a></li>
  <li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c">Rabin-Karp string matching</a> is used for compression.</li>
  <li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/native_client/src/trusted/validator_ragel/dfa_traversal.py">Compute the suffixes of an automaton</a>.</li>
  <li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit/Source/wtf/BloomFilter.h">Bloom filter</a> implemented by Apple Inc.</li>
  <li><a href="https://code.google.com/p/chromium/codesearch#chromium/src/third_party/libvpx/source/libvpx/vp8/common/textblit.c">Bresenham's algorithm</a>.</li>
  </ol>
  <h2>Programming Language Libraries</h2></p>
</blockquote>

<p>I think they are worth considering. The programming languages designers thought it was worth the time and effort of some engineers to implement these data structures and algorithms so others would not have to. The existence of libraries is part of the reason we can find basic data structures reimplemented in software that is written in C but less so for Java applications. </p>

<ol>
<li>
The <a href="http://www.cplusplus.com/reference/stl/">C++ STL</a> includes lists, stacks, queues, maps, vectors, and algorithms for <a href="http://www.cplusplus.com/reference/algorithm/">sorting, searching and heap manipulation</a>. </li>
<li><a href="http://docs.oracle.com/javase/7/docs/api/">The Java API</a> is very extensive and covers much more.</li>
<li>The <a href="http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html/index.html#algorithm.description_and_rationale">Boost C++ library</a> includes algorithms like Boyer-Moore and Knuth-Morris-Pratt string matching algorithms.</li>
</ol>

<h2>Allocation and Scheduling Algorithms</h2>

<p>I find these interesting because even though they are called heuristics, the policy you use dictates the type of algorithm and data structure that are required, so one need to know about stacks and queues. </p>

<ol>
<li>Least Recently Used can be implemented in multiple ways. A <a href="https://github.com/mirrors/linux-2.6/blob/master/include/linux/list_lru.h">list-based implementation</a> in the Linux kernel.</li>
<li>Other possibilities are First In First Out, Least Frequently Used, and Round Robin. </li>
<li>A variant of FIFO was used by the VAX/VMS system.</li>
<li><a href="http://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock">The Clock algorithm</a> by <a href="http://dl.acm.org/citation.cfm?id=4750">Richard Carr</a> is used for page frame replacement in Linux.</li>
<li>The Intel i860 processor used a random replacement policy.</li>
<li><a href="http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache">Adaptive Replacement Cache</a> is used in some IBM storage controllers, and was used in PostgreSQL though <a href="http://www.varlena.com/GeneralBits/96.php">only briefly due to patent concerns</a>. </li>
<li>The <a href="http://en.wikipedia.org/wiki/Buddy_memory_allocation">Buddy memory allocation algorithm</a>, which is discussed by Knuth in TAOCP Vol. 1 is used in the Linux kernel, and the jemalloc concurrent allocator used by FreeBSD and in <a href="http://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919">facebook</a>.</li>
</ol>

<h2> Core utils in *nix systems</h2>

<ol>
<li><em>grep</em> and <em>awk</em> both implement the Thompson-McNaughton-Yamada construction of NFAs from regular expressions, which apparently <a href="http://swtch.com/~rsc/regexp/regexp1.html">even beats the Perl implementation</a>. </li>
<li><em>tsort</em> implements topological sort.</li>
<li><em>fgrep</em> implements the <a href="http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm">Aho-Corasick string matching algorithm.</a></li>
<li><em>GNU grep</em>, <a href="http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html">implements the Boyer-Moore algorithm</a> according to the author Mike Haertel. </li>
<li>crypt(1) on Unix implemented a variant of the encryption algorithm in the Enigma machine.</li>
<li><em><a href="http://www.cs.dartmouth.edu/~doug/diff.pdf">Unix diff</a></em> implemented by Doug McIllroy, based on a prototype co-written with James Hunt, performs better than the standard dynamic programming algorithm used to compute Levenshtein distances. The <a href="http://linux.die.net/man/3/diff">Linux version</a> computes the shortest edit distance. </li>
</ol>

<h2>Cryptographic Algorithms</h2>

<p>This could be a very long list. Cryptographic algorithms are implemented in all software that can perform secure communications or transactions.</p>

<ol>
<li><a href="http://en.wikipedia.org/wiki/Merkle_tree">Merkle trees</a>, specifically the Tiger Tree Hash variant, were used in peer-to-peer applications such as <a href="https://github.com/gtk-gnutella/bitter">GTK Gnutella</a> and <a href="http://en.wikibooks.org/wiki/LimeWire">LimeWire</a>.</li>
<li><a href="http://en.wikipedia.org/wiki/MD5">MD5</a> is used to provide a checksum for software packages and is used for integrity checks on *nix systems (<a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/crypto/md5.c">Linux implementation</a>) and is also supported on Windows and OS X.</li>
<li><a href="http://www.openssl.org/">OpenSSL</a> implements many cryptographic algorithms including AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.</li>
</ol>

<h2>Compilers</h2>

<ol>
<li><a href="http://en.wikipedia.org/wiki/LALR_parser">LALR parsing</a> is implemented by yacc and bison.</li>
<li>Dominator algorithms are used in most optimizing compilers based on SSA form.</li>
<li><em>lex</em> and <em>flex</em> compile regular expressions into NFAs. </li>
</ol>

<h2>Compression and Image Processing </h2>

<ol>
<li><a href="http://en.wikipedia.org/wiki/Lempel_Ziv">The Lempel-Ziv</a> algorithms for the GIF image format are implemented in image manipulation programs, starting from the *nix utility <em>convert</em> to complex programs.</li>
<li>Run length encoding is used to generate PCX files (used by the original Paintbrush program), compressed BMP files and TIFF files.</li>
<li>Wavelet compression is the basis for JPEG 2000 so all digital cameras that produce JPEG 2000 files will be implementing this algorithm. </li>
<li>Reed-Solomon error correction is implemented in <a href="https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/reed_solomon/reed_solomon.c">the Linux kernel</a>, CD drives, barcode readers and was combined with convolution for image transmission from Voyager.</li>
</ol>

<h2>Conflict Driven Clause Learning</h2>

<p>Since the year 2000, the running time of SAT solvers on industrial benchmarks (usually from the hardware industry, though though other sources are used too) has decreased nearly exponentially every year. A very important part of this development is the <em>Conflict Driven Clause Learning</em> algorithm that combines the <em>Boolean Constraint Propagation</em> algorithm in the original paper of Davis Logemann and Loveland with the technique of clause learning that originated in constraint programming and artificial intelligence research. For specific, industrial modelling, SAT is considered an easy problem (<a href="http://rjlipton.wordpress.com/2009/07/13/sat-solvers-is-sat-hard-or-easy/">see this discussion</a>). To me, this is one of the greatest success stories in recent times because it combines algorithmic advances spread over several years, clever engineering ideas, experimental evaluation, and a concerted communal effort to solve the problem. The <a href="http://dl.acm.org/citation.cfm?id=1536637">CACM article by Malik and Zhang</a> is a good read. This algorithm is taught in many universities (I have attended four where it was the case) but typically in a logic or formal methods class. </p>

<p>Applications of SAT solvers are numerous. IBM, Intel and many other companies have their own SAT solver implementations. The <a href="http://en.opensuse.org/Portal%3aLibzypp">package manager</a> in OpenSUSE also uses a SAT solver.</p>

CC BY-SA 3.0
2013-11-13T01:48:39.580Z
Nice list, but I'm not sure about including the OS scheduling algorithms and CDCL since they are heuristic and in the worst-case can be quite bad.
Huck Bennett
CC BY-SA 3.0
2013-11-13T02:01:57.547Z
@HuckBennett, CDCL is an algorithm parameterized by heuristics but is not itself a heuristic. It has worst case exponential behaviour but it is non-trivial to show that. Moreover, we cannot do provably better and it is the best we can do in practice, so I feel all computer scientists should know about it! As for LRU,FIFO, etc.  they are heuristics, but, as with ARC, may require clever algorithms or data structures to implement.
Vijay D
CC BY-SA 3.0
2013-11-13T03:51:10.250Z
I'm not saying that CDCL isn't cool or important (it is) but I don't think it's really an algorithm as is usually meant in theory since we can't really prove anything about it. "Here's an algorithm that seems to work well in practice" is more the domain of AI and formal methods. AFAIK it has $O(2^n)$ worst-case running time and no other guarantees using other formal analyses. We actually can do better for various NP-complete variants of SAT such as Schoning's $O^*(1.334)$-time algorithm for 3-SAT.
Huck Bennett
CC BY-SA 3.0
2013-11-13T08:43:58.823Z
Wouldn't such a comment have applied to Simplex: initially not well understood and later shown to be exponential but works in practice and much later shown to have polynomial smoothed complexity? CDCL is interesting for algorithm analysis because you need to go via proof complexity to derive families of formulae exhibiting worst case behaviour, and also to show it can be exponentially more succinct than some variants of resolution. There are various extensions, such as symmetry breaking and autarky techniques for which such an analysis is still open.
Vijay D
CC BY-SA 3.0
2013-11-13T11:27:55.323Z
@VijayD Thanks for the interesting list.  I find the use of Red-Black trees in the Linux kernel compelling.
Manu
CC BY-SA 3.0
2013-11-13T14:18:42.783Z
Good point about simplex.
Huck Bennett
CC BY-SA 3.0
2013-11-14T16:13:09.300Z
Nice update!  I like the list of basic data structures that show up in the Linux kernel.  Ideally, it would be great if one could find more examples like that but that are not strictly confined to data structures.
Manu
CC BY-SA 3.0
2013-11-14T17:30:24.803Z
@EmanueleViola, please elaborate. By more examples, do you mean more systems, or do you mean, more algorithms in the same system? What would you like to see beyond data structures? (maybe add it to the original question)
Vijay D
CC BY-SA 3.0
2013-11-14T20:01:10.297Z
This is a treasure for a student
neo1691
CC BY-SA 3.0
2013-11-15T12:35:36.037Z
@VijayD: I mean more algorithms in some system.  E.g. notable members of sorting, dynamic programming, greedy, flow, LP, graph algorithms, approx algorithms, string matching, number-theoretic, and whatever else you think is core material.
Manu
CC BY-SA 3.0
2013-11-17T04:32:31.300Z
@EmanueleViola, I've added a few more examples. The post is long now, so I don't want to extend it. Maybe you should ask a new question specifically about implementations of Dijkstra, Simplex, Bloom filters as part of a real system like Linux, Chrome, a web server etc. I think you are more likely to get good answers if you are specific.
Vijay D
CC BY-SA 3.0
2013-11-24T10:59:14.297Z
wow, did you managed to write down the list off the top of your head? :)
DRC
CC BY-SA 3.0
2013-11-24T18:25:50.557Z
Wow, is this the most upvoted answer on cstheory now :)? Did someone post this question on reddit?
Sasho Nikolov
CC BY-SA 3.0
2013-11-24T20:03:45.553Z
Hacker news and r/programming.
Vijay D
CC BY-SA 3.0
2013-11-28T06:18:01.247Z
One of these days, I am going to add Wikipedia links along with the source code links. (unless someone else does it before.)
lprsd
CC BY-SA 3.0
2013-11-13T00:33:52.410Z
2013-11-24T11:48:02.943Z
2013-11-24T11:48:02.943Z
Vijay D
<p>To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of examples where core algorithms have been deployed in commercial, governmental, or widely-used software/hardware.</p>
<p>I am looking for such examples that satisfy the following criteria:</p>
<ol>
<li><p>The software/hardware using the algorithm should be in wide use right now.</p>
</li>
<li><p>The example should be specific.
Please give a reference to a specific system and a specific algorithm.<br />
E.g., in &quot;algorithm X is useful for image processing&quot;
the term &quot;image processing&quot; is not specific enough;
in &quot;Google search uses graph algorithms&quot;
the term &quot;graph algorithms&quot; is not specific enough.</p>
</li>
<li><p>The algorithm should be taught in
typical undergraduate or Ph.D. classes in algorithms or data structures.
Ideally, the algorithm is covered in typical algorithms textbooks.
E.g., &quot;well-known system X uses little-known algorithm Y&quot; is not good.</p>
</li>
</ol>
<hr />
<h3>Update:</h3>
<p>Thanks again for the great answers and links!
Some people comment that it is hard to satisfy the criteria
because core algorithms are so pervasive that it's hard to point to a specific use.
I see the difficulty.
But I think it is worthwhile to come up with specific examples because
in my experience telling people:
&quot;Look, algorithms are important because they are <em>just about everywhere</em>!&quot; does not work.</p>

CC BY-SA 4.0
2018-09-03T05:56:27.987Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/82645/discussion-on-question-by-emanuele-viola-core-algorithms-deployed).
Bjørn Kjos-Hanssen
<ds.algorithms><big-picture><application-of-theory>
Core algorithms deployed
Manu
# Core algorithms deployed

(Asked by: username_0 on 2013-11-12)

To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of examples where core algorithms have been deployed in commercial, governmental, or widely-used software/hardware.

I am looking for such examples that satisfy the following criteria:

1. The software/hardware using the algorithm should be in wide use right now.
2. The example should be specific.
   Please give a reference to a specific system and a specific algorithm.  
   E.g., in "algorithm X is useful for image processing"
   the term "image processing" is not specific enough;
   in "Google search uses graph algorithms"
   the term "graph algorithms" is not specific enough.
3. The algorithm should be taught in
   typical undergraduate or Ph.D. classes in algorithms or data structures.
   Ideally, the algorithm is covered in typical algorithms textbooks.
   E.g., "well-known system X uses little-known algorithm Y" is not good.

---

### Update:

Thanks again for the great answers and links!
Some people comment that it is hard to satisfy the criteria
because core algorithms are so pervasive that it's hard to point to a specific use.
I see the difficulty.
But I think it is worthwhile to come up with specific examples because
in my experience telling people:
"Look, algorithms are important because they are *just about everywhere*!" does not work.

**Tags:** ds.algorithms, big-picture, application-of-theory
> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/82645/discussion-on-question-by-emanuele-viola-core-algorithms-deployed).  

---

## 29 answers

### Answer by username_6 on 2013-11-13. Score: 498 | Accepted answer

Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashionable algorithms course material such as Strassen's multiplication, the AKS primality test, or the Moser-Tardos algorithm is relevant for low-level practical problems of implementing a video database, an optimizing compiler, an operating system, a network congestion control system or any other system. The value of these courses is learning that there are intricate ways to exploit the structure of a problem to find efficient solutions. Advanced algorithms is also where one meets simple algorithms whose analysis is non-trivial. For this reason, I would not dismiss simple randomized algorithms or PageRank.

I think you can choose any large piece of software and find basic and advanced algorithms implemented in it. As a case study, I've done this for the Linux kernel, and shown a few examples from Chromium.

## Basic Data Structures and Algorithms in the Linux kernel

Links are to the [source code on github](https://github.com/mirrors/linux-2.6).

1. [Linked list](https://github.com/mirrors/linux-2.6/blob/master/lib/llist.c), [doubly linked list](https://github.com/mirrors/linux-2.6/blob/master/include/linux/list.h), [lock-free linked list](https://github.com/mirrors/linux-2.6/blob/master/include/linux/llist.h).
2. [B+ Trees](https://github.com/mirrors/linux-2.6/blob/39caa0916ef27cf1da5026eb708a2b8413156f75/lib/btree.c) with comments telling you what you can't find in the textbooks.

   > A relatively simple B+Tree implementation. I have written it as a learning exercise to understand how B+Trees work. Turned out to be useful as well.
   >
   > ...
   >
   > A tricks was used that is not commonly found in textbooks. The lowest values are to the right, not to the left. All used slots within a node are on the left, all unused slots contain NUL values. Most operations simply loop once over all slots and terminate on the first NUL.
3. [Priority sorted lists](https://github.com/mirrors/linux-2.6/blob/master/include/linux/plist.h) used for [mutexes](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/rtmutex.h), [drivers](https://github.com/mirrors/linux-2.6/blob/f0d55cc1a65852e6647d4f5d707c1c9b5471ce3c/drivers/powercap/intel_rapl.c), etc.
4. [Red-Black trees](https://github.com/mirrors/linux-2.6/blob/master/include/linux/rbtree.h) are [used](http://lwn.net/Articles/184495/) for scheduling, virtual memory management, to track file descriptors and directory entries,etc.
5. [Interval trees](https://github.com/mirrors/linux-2.6/blob/master/include/linux/interval_tree.h)
6. [Radix trees](https://github.com/mirrors/linux-2.6/blob/master/include/linux/radix-tree.h), are used for [memory management](http://lwn.net/Articles/175432/), NFS related lookups and networking related functionality.

   > A common use of the radix tree is to store pointers to struct pages;
7. [Priority heap](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/prio_heap.h), which is literally, a textbook implementation, used in the [control group system](https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/include/linux/cgroup.h).

   > Simple insertion-only static-sized priority heap containing pointers, based on CLR, chapter 7
8. [Hash functions](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/hash.h), with a reference to Knuth and to a paper.

   > Knuth recommends primes in approximately golden ratio to the maximum
   > integer representable by a machine word for multiplicative hashing.
   > Chuck Lever verified the effectiveness of this technique:
   >
   > <http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf>
   >
   > These primes are chosen to be bit-sparse, that is operations on
   > them can use shifts and additions instead of multiplications for
   > machines where multiplications are slow.
9. Some parts of the code, such as [this driver](https://github.com/mirrors/linux-2.6/blob/0b1e73ed225d8f7aeef96b74147215ca8b990dce/drivers/staging/lustre/lustre/lov/lov_pool.c), implement their own hash function.

   > hash function using a Rotating Hash algorithm
   >
   > Knuth, D. The Art of Computer Programming,
   > Volume 3: Sorting and Searching,
   > Chapter 6.4.
   > Addison Wesley, 1973
10. [Hash tables](https://github.com/mirrors/linux-2.6/blob/master/include/linux/hashtable.h) used to implement [inodes](https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/inode.c), [file system integrity checks](https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/check-integrity.c) etc.
11. [Bit arrays](https://github.com/mirrors/linux-2.6/blob/master/include/linux/bitmap.h), which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
12. [Semaphores](https://github.com/mirrors/linux-2.6/blob/master/include/linux/semaphore.h) and [spin locks](https://github.com/mirrors/linux-2.6/blob/master/include/linux/spinlock.h)
13. [Binary search](https://github.com/mirrors/linux-2.6/blob/master/lib/bsearch.c) is used for [interrupt handling](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/drivers/sh/intc/chip.c), [register cache lookup](https://github.com/mirrors/linux-2.6/blob/10d0c9705e80bbd3d587c5fad24599aabaca6688/drivers/base/regmap/regcache.c), etc.
14. [Binary search with B-trees](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/befs/btree.c)
15. [Depth first search](https://github.com/mirrors/linux-2.6/blob/a9238741987386bb549d61572973c7e62b2a4145/drivers/acpi/acpica/nswalk.c) and variant used in [directory configuration](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/configfs/dir.c).

    > Performs a modified depth-first walk of the namespace tree, starting
    > (and ending) at the node specified by start\_handle. The callback
    > function is called whenever a node that matches the type parameter is
    > found. If the callback function returns a non-zero value, the search
    > is terminated immediately and this value is returned to the caller.
16. [Breadth first search](https://github.com/mirrors/linux-2.6/blob/4fbf888accb39af423f271111d44e8186f053723/kernel/locking/lockdep.c) is used to check correctness of locking at runtime.
17. [Merge sort](https://github.com/mirrors/linux-2.6/blob/master/lib/list_sort.c) on linked lists is used for [garbage collection](https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/ubifs/gc.c), [file system management](https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/raid56.c), etc.
18. [Bubble sort](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/drivers/media/common/saa7146/saa7146_hlp.c) is amazingly implemented too, in a driver library.
19. [Knuth-Morris-Pratt string matching](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_kmp.c),

    > Implements a linear-time string-matching algorithm due to Knuth,
    > Morris, and Pratt [1]. Their algorithm avoids the explicit
    > computation of the transition function DELTA altogether. Its
    > matching time is O(n), for n being length(text), using just an
    > auxiliary function PI[1..m], for m being length(pattern),
    > precomputed from the pattern in time O(m). The array PI allows
    > the transition function DELTA to be computed efficiently
    > "on the fly" as needed. Roughly speaking, for any state
    > "q" = 0,1,...,m and any character "a" in SIGMA, the value
    > PI["q"] contains the information that is independent of "a" and
    > is needed to compute DELTA("q", "a") [2](https://github.com/mirrors/linux-2.6/blob/master/lib/llist.c). Since the array PI
    > has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
    > save a factor of |SIGMA| in the preprocessing time by computing
    > PI rather than DELTA.
    >
    > [1] Cormen, Leiserson, Rivest, Stein
    > Introdcution to Algorithms, 2nd Edition, MIT Press
    >
    > [2] See finite automation theory
20. [Boyer-Moore pattern matching](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_bm.c) with references and recommendations for when to prefer the alternative.

    > Implements Boyer-Moore string matching algorithm:
    >
    > [1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
    > Communications of the Association for Computing Machinery,
    > 20(10), 1977, pp. 762-772.
    > <http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf>
    >
    > [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq,
    > 2004
    > <http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf>
    >
    > Note: Since Boyer-Moore (BM) performs searches for matchings from
    > right
    > to left, it's still possible that a matching could be spread over
    > multiple blocks, in that case this algorithm won't find any
    > coincidence.
    >
    > If you're willing to ensure that such thing won't ever happen,
    > use the
    > Knuth-Pratt-Morris (KMP) implementation instead. In conclusion,
    > choose
    > the proper string search algorithm depending on your setting.
    >
    > Say you're using the textsearch infrastructure for filtering,
    > NIDS or  
    > any similar security focused purpose, then go KMP. Otherwise, if
    > you
    > really care about performance, say you're classifying packets to
    > apply
    > Quality of Service (QoS) policies, and you don't mind about
    > possible
    > matchings spread over multiple fragments, then go BM.

## Data Structures and Algorithms in the Chromium Web Browser

Links are to the [source code on Google code](https://code.google.com/p/chromium/). I'm only going to list a few. I would suggest using the search feature to look up your favourite algorithm or data structure.

1. [Splay trees](https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/splay-tree.h).

> The tree is also parameterized by an allocation policy
> (Allocator). The policy is used for allocating lists in the C free
> store or the zone; see zone.h.- [Voronoi diagrams](https://code.google.com/p/chromium/codesearch#chromium/src/native_client_sdk/src/examples/demo/voronoi/index.html) are used in a demo.
> - [Tabbing based on Bresenham's algorithm](https://code.google.com/p/chromium/codesearch#chromium/src/chrome/browser/ui/cocoa/tabs/tab_strip_controller.mm).
> There are also such data structures and algorithms in the third-party code included in the Chromium code.

1. [Binary trees](https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/bintree.py)
2. [Red-Black trees](https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/rbtree.py)

> Conclusion of Julian Walker
>
> Red black trees are interesting beasts. They're believed to be
> simpler than
> AVL trees (their direct competitor), and at first glance this seems
> to be the
> case because insertion is a breeze. However, when one begins to play
> with the
> deletion algorithm, red black trees become very tricky. However, the
> counterweight to this added complexity is that both insertion and
> deletion
> can be implemented using a single pass, top-down algorithm. Such is
> not the
> case with AVL trees, where only the insertion algorithm can be
> written top-down.
> Deletion from an AVL tree requires a bottom-up algorithm.
>
> ...
>
> Red black trees are popular, as most data structures with a
> whimsical name.
> For example, in Java and C++, the library map structures are
> typically
> implemented with a red black tree. Red black trees are also
> comparable in
> speed to AVL trees. While the balance is not quite as good, the work
> it takes
> to maintain balance is usually better in a red black tree. There are
> a few
> misconceptions floating around, but for the most part the hype about
> red black
> trees is accurate.- [AVL trees](https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/avltree.py)
> - [Rabin-Karp string matching](https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c) is used for compression.
> - [Compute the suffixes of an automaton](https://code.google.com/p/chromium/codesearch#chromium/src/native_client/src/trusted/validator_ragel/dfa_traversal.py).
> - [Bloom filter](https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit/Source/wtf/BloomFilter.h) implemented by Apple Inc.
> - [Bresenham's algorithm](https://code.google.com/p/chromium/codesearch#chromium/src/third_party/libvpx/source/libvpx/vp8/common/textblit.c).
>
> ## Programming Language Libraries

I think they are worth considering. The programming languages designers thought it was worth the time and effort of some engineers to implement these data structures and algorithms so others would not have to. The existence of libraries is part of the reason we can find basic data structures reimplemented in software that is written in C but less so for Java applications.

1. The [C++ STL](http://www.cplusplus.com/reference/stl/) includes lists, stacks, queues, maps, vectors, and algorithms for [sorting, searching and heap manipulation](http://www.cplusplus.com/reference/algorithm/).
2. [The Java API](http://docs.oracle.com/javase/7/docs/api/) is very extensive and covers much more.
3. The [Boost C++ library](http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html/index.html#algorithm.description_and_rationale) includes algorithms like Boyer-Moore and Knuth-Morris-Pratt string matching algorithms.

## Allocation and Scheduling Algorithms

I find these interesting because even though they are called heuristics, the policy you use dictates the type of algorithm and data structure that are required, so one need to know about stacks and queues.

1. Least Recently Used can be implemented in multiple ways. A [list-based implementation](https://github.com/mirrors/linux-2.6/blob/master/include/linux/list_lru.h) in the Linux kernel.
2. Other possibilities are First In First Out, Least Frequently Used, and Round Robin.
3. A variant of FIFO was used by the VAX/VMS system.
4. [The Clock algorithm](http://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock) by [Richard Carr](http://dl.acm.org/citation.cfm?id=4750) is used for page frame replacement in Linux.
5. The Intel i860 processor used a random replacement policy.
6. [Adaptive Replacement Cache](http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache) is used in some IBM storage controllers, and was used in PostgreSQL though [only briefly due to patent concerns](http://www.varlena.com/GeneralBits/96.php).
7. The [Buddy memory allocation algorithm](http://en.wikipedia.org/wiki/Buddy_memory_allocation), which is discussed by Knuth in TAOCP Vol. 1 is used in the Linux kernel, and the jemalloc concurrent allocator used by FreeBSD and in [facebook](http://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919).

## Core utils in \*nix systems

1. *grep* and *awk* both implement the Thompson-McNaughton-Yamada construction of NFAs from regular expressions, which apparently [even beats the Perl implementation](http://swtch.com/~rsc/regexp/regexp1.html).
2. *tsort* implements topological sort.
3. *fgrep* implements the [Aho-Corasick string matching algorithm.](http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm)
4. *GNU grep*, [implements the Boyer-Moore algorithm](http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html) according to the author Mike Haertel.
5. crypt(1) on Unix implemented a variant of the encryption algorithm in the Enigma machine.
6. *[Unix diff](http://www.cs.dartmouth.edu/~doug/diff.pdf)* implemented by Doug McIllroy, based on a prototype co-written with James Hunt, performs better than the standard dynamic programming algorithm used to compute Levenshtein distances. The [Linux version](http://linux.die.net/man/3/diff) computes the shortest edit distance.

## Cryptographic Algorithms

This could be a very long list. Cryptographic algorithms are implemented in all software that can perform secure communications or transactions.

1. [Merkle trees](http://en.wikipedia.org/wiki/Merkle_tree), specifically the Tiger Tree Hash variant, were used in peer-to-peer applications such as [GTK Gnutella](https://github.com/gtk-gnutella/bitter) and [LimeWire](http://en.wikibooks.org/wiki/LimeWire).
2. [MD5](http://en.wikipedia.org/wiki/MD5) is used to provide a checksum for software packages and is used for integrity checks on \*nix systems ([Linux implementation](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/crypto/md5.c)) and is also supported on Windows and OS X.
3. [OpenSSL](http://www.openssl.org/) implements many cryptographic algorithms including AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.

## Compilers

1. [LALR parsing](http://en.wikipedia.org/wiki/LALR_parser) is implemented by yacc and bison.
2. Dominator algorithms are used in most optimizing compilers based on SSA form.
3. *lex* and *flex* compile regular expressions into NFAs.

## Compression and Image Processing

1. [The Lempel-Ziv](http://en.wikipedia.org/wiki/Lempel_Ziv) algorithms for the GIF image format are implemented in image manipulation programs, starting from the \*nix utility *convert* to complex programs.
2. Run length encoding is used to generate PCX files (used by the original Paintbrush program), compressed BMP files and TIFF files.
3. Wavelet compression is the basis for JPEG 2000 so all digital cameras that produce JPEG 2000 files will be implementing this algorithm.
4. Reed-Solomon error correction is implemented in [the Linux kernel](https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/reed_solomon/reed_solomon.c), CD drives, barcode readers and was combined with convolution for image transmission from Voyager.

## Conflict Driven Clause Learning

Since the year 2000, the running time of SAT solvers on industrial benchmarks (usually from the hardware industry, though though other sources are used too) has decreased nearly exponentially every year. A very important part of this development is the *Conflict Driven Clause Learning* algorithm that combines the *Boolean Constraint Propagation* algorithm in the original paper of Davis Logemann and Loveland with the technique of clause learning that originated in constraint programming and artificial intelligence research. For specific, industrial modelling, SAT is considered an easy problem ([see this discussion](http://rjlipton.wordpress.com/2009/07/13/sat-solvers-is-sat-hard-or-easy/)). To me, this is one of the greatest success stories in recent times because it combines algorithmic advances spread over several years, clever engineering ideas, experimental evaluation, and a concerted communal effort to solve the problem. The [CACM article by Malik and Zhang](http://dl.acm.org/citation.cfm?id=1536637) is a good read. This algorithm is taught in many universities (I have attended four where it was the case) but typically in a logic or formal methods class.

Applications of SAT solvers are numerous. IBM, Intel and many other companies have their own SAT solver implementations. The [package manager](http://en.opensuse.org/Portal%3aLibzypp) in OpenSUSE also uses a SAT solver.

> **Comments:**
> **username_2**: Nice list, but I'm not sure about including the OS scheduling algorithms and CDCL since they are heuristic and in the worst-case can be quite bad.  
> **username_6**: @HuckBennett, CDCL is an algorithm parameterized by heuristics but is not itself a heuristic. It has worst case exponential behaviour but it is non-trivial to show that. Moreover, we cannot do provably better and it is the best we can do in practice, so I feel all computer scientists should know about it! As for LRU,FIFO, etc.  they are heuristics, but, as with ARC, may require clever algorithms or data structures to implement.  
> **username_2**: I'm not saying that CDCL isn't cool or important (it is) but I don't think it's really an algorithm as is usually meant in theory since we can't really prove anything about it. "Here's an algorithm that seems to work well in practice" is more the domain of AI and formal methods. AFAIK it has $O(2^n)$ worst-case running time and no other guarantees using other formal analyses. We actually can do better for various NP-complete variants of SAT such as Schoning's $O^*(1.334)$-time algorithm for 3-SAT.  
> **username_6**: Wouldn't such a comment have applied to Simplex: initially not well understood and later shown to be exponential but works in practice and much later shown to have polynomial smoothed complexity? CDCL is interesting for algorithm analysis because you need to go via proof complexity to derive families of formulae exhibiting worst case behaviour, and also to show it can be exponentially more succinct than some variants of resolution. There are various extensions, such as symmetry breaking and autarky techniques for which such an analysis is still open.  
> **username_0**: @VijayD Thanks for the interesting list.  I find the use of Red-Black trees in the Linux kernel compelling.  
> **username_2**: Good point about simplex.  
> **username_0**: Nice update!  I like the list of basic data structures that show up in the Linux kernel.  Ideally, it would be great if one could find more examples like that but that are not strictly confined to data structures.  
> **username_6**: @EmanueleViola, please elaborate. By more examples, do you mean more systems, or do you mean, more algorithms in the same system? What would you like to see beyond data structures? (maybe add it to the original question)  
> **username_40**: This is a treasure for a student  
> **username_0**: @VijayD: I mean more algorithms in some system.  E.g. notable members of sorting, dynamic programming, greedy, flow, LP, graph algorithms, approx algorithms, string matching, number-theoretic, and whatever else you think is core material.  
> **username_6**: @EmanueleViola, I've added a few more examples. The post is long now, so I don't want to extend it. Maybe you should ask a new question specifically about implementations of Dijkstra, Simplex, Bloom filters as part of a real system like Linux, Chrome, a web server etc. I think you are more likely to get good answers if you are specific.  
> **username_41**: wow, did you managed to write down the list off the top of your head? :)  
> **username_10**: Wow, is this the most upvoted answer on cstheory now :)? Did someone post this question on reddit?  
> **username_6**: Hacker news and r/programming.  
> **username_42**: One of these days, I am going to add Wikipedia links along with the source code links. (unless someone else does it before.)  

---

### Answer by username_2 on 2013-11-12. Score: 42

[PageRank](http://en.wikipedia.org/wiki/Pagerank) is one of the best-known such algorithms. Developed by Google co-founder Larry Page and co-authors, it formed the basis of Google's original search engine and is [widely credited](http://blog.computationalcomplexity.org/2013/07/altavista-versus-google.html) with helping them to achieve better search results than their competitors at the time.

We imagine a "random surfer" starting at some webpage, and repeatedly clicking a random link to take him to a new page. The question is, "What fraction of the time will the surfer spend at each page?" The more time the surfer spends at a page, the more important the page is considered.

More formally, we view the internet as a graph where pages are nodes and links are directed edges. We can then model the surfer's action as a random walk on a graph or equivalently as a Markov Chain with transition matrix $M$. After dealing with some issues to ensure that the Markov Chain is ergodic (where does the surfer go if a page has no outgoing links?), we compute the amount of time the surfer spends at each page as the steady state distribution of the Markov Chain.

The algorithm itself is in some sense trivial - we just compute $M^k \pi\_0$ for large $k$ and arbitrary initial distribution $\pi\_0$. This just amounts to repeated matrix-matrix or matrix-vector multiplication. The algorithms content is mainly in the set-up (ensuring ergodicity, proving that an ergodic Markov Chain has a unique steady state distribution) and convergence analysis (dependence on the spectral gap of $M$).

> **Comments:**
> **username_0**: I don't think this is typical algorithms material.  
> **username_2**: Incidentally I first learned about PageRank in an algorithms class. In fact, I think the professor chose it because it was a nice example of "algorithms used in practice." If you limit examples to "first half of CLRS" type material, the list of examples will either be too long or too trivial -- quicksort, B-trees, and Dijkstra's algorithm are ubiquitous.  
> **username_3**: @EmanueleViola I am currently an information science student at a university. I have not taken algorithms but I have had Markov chains and PageRank in other classes  
> **username_4**: We teach PageRank to undergraduates.  
> **username_5**: I teach it to undergraduates also (both in the required algorithms class and in a more specialized graph algorithms elective).  
> **username_6**: I learnt PageRank as an undergraduate in an elective.  
> **username_0**: Alright, PageRank should qualify even though it's not in standard textbooks (I think).  Though the algorithm is a bit atypical (when compared to other core algorithms), because as Huck says it's pretty much all in the analysis.  
> **username_7**: Isn't pagerank supposed to be based on the number of backlinks from other pages? You say it is based on the time that a user spends on a page; which is data a search engine cannot have.  
> **username_2**: Here "time" means the fraction of steps in the Markov Chain that the user spends at the page.  
> **username_8**: You forgot to mention the father of PageRank: the Hub-Authority algorithm. In my opinion, it's a far more commonly studied algorithm, because it's simpler and the subsequent algorithms like PageRank can be easily derived as enhancements.  

---

### Answer by username_9 on 2013-11-12. Score: 35

I would mention the widely-used software CPLEX (or similar) implementation of the Simplex method/algorithm
for solving linear programming problems.
It is the (?) most used algorithm in economy and operations research.

*"If one would take statistics about which mathematical
problem is using up most of the computer time in the
world, then (not counting database handling problems
like sorting and searching) the answer would probably be
linear programming.*" (L. Lovász, A new linear programming algorithm-better
or worse than the simplex method? Math. Intelligencer 2 (3) (1979/80) 141-146.)

The Simplex algorithm has also great influence in theory; see, for instance,
the [(Polynomial) Hirsch Conjecture](https://cstheory.stackexchange.com/questions/1814/a-combinatorial-version-for-the-polynomial-hirsch-conjecture).

I guess a typical undergraduate or Ph.D. class in algorithms deals with the Simplex algorithm
(including basic algorithms from linear algebra like Gauss Elimination Method).

(Other successful algorithms, including Quicksort for sorting, are listed in
[Algorithms from the Book](https://cstheory.stackexchange.com/questions/189/algorithms-from-the-book).)

> **Comments:**
> **username_0**: "economy and operations research" isn't specific enough.  CPLEX isn't the type of example I was looking for either, as it is just an implementation of the algorithm; it would be different if, say, the gcc compiler used the simplex method.  
> **username_9**: I think "linear programming problems" is specific enough when we speak about economy and OR. Also, by CPLEX   I meant the algorithm behind the implementation.  
> **username_10**: "Today, most large firms use linear programming to price products and manage supply chains. Transportation firms use it to choose the cheapest way to consolidate, coordinate and route shipments of many products from globally distributed suppliers to distant markets subject to capacity constraints. The petroleum industry uses it for exploration, blending, production scheduling and distribution. The iron and steel industry uses it to evaluate iron ores, explore the addition of coke ovens and select products..." http://news.stanford.edu/news/2005/may25/dantzigobit-052505.html  
> **username_0**: Thanks.  But I find the quote terribly vague.  I think if I say that in front of a class of students, half of it would fall asleep ;-)  It would be different if we say something like: UPS uses LP to ship packages as follows... I am not saying such examples are trivial to find, but given that "most large firms use LP" I'd hope we can at least point to *one*.  
> **username_10**: Off the top of my head, since 2007 LAX (the airport) has used software for solving Stackelberg games to schedule the security personnel. Solving large LPs is part of the whole thing, see e.g. http://teamcore.usc.edu/ARMOR-LAX/. Besides that, I would ask someone from your Operations Research department: they would usually have plenty of war stories about using LP in real life  

---

### Answer by username_11 on 2013-11-12. Score: 31

As I understand it, the [National Resident Matching Program](http://en.wikipedia.org/wiki/National_Resident_Matching_Program) was for a long time just a straight application of the [Gale-Shapley algorithm](http://en.wikipedia.org/wiki/Stable_marriage_problem) for the stable marriage problem. It has since been slightly updated to handle some extra details like spousal assignments (aka the "two-body problem"), etc...

> **Comments:**
> **username_0**: I am not sure stable marriage is typical algorithms material.  
> **username_10**: It's in the Tardos and Kleinberg Algorithms Design book, and also in Motwani's Randomized Algorithms, and both books are widely used. Stable marriage may not be universally taught in algorithms courses, but it certainly is taught in a lot of them.  
> **username_11**: A quick search reveals that it has shown up in [Berkeley's CS70](http://www.cs.berkeley.edu/~daw/teaching/cs70-s08/notes/n7.pdf), [MIT's 6.042](http://courses.csail.mit.edu/6.042/fall11/slides8w.pdf), [UMD's CMSC451](https://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec01-stable.pdf), etc...  
> **username_12**: Interestingly, when you add in spousal assignments, the problem becomes NP-complete: http://arxiv.org/abs/1308.4534. However, in practice this seems not to cause too much of a problem: http://en.wikipedia.org/wiki/National_Resident_Matching_Program#Couples  
> **username_13**: @EmanueleViola while it might not be covered traditionally, its inclusion in the Kleinberg/Tardos book has made it more popular, (and if not it should be !)  
> **username_0**: I agree that the inclusion in Kleinberg Tardos' book makes this qualify.  

---

### Answer by username_11 on 2013-11-12. Score: 24

If you're also including PhD-level stuff, many (most?) graduate CS programs include some course in coding theory. If you have a course in coding theory, you will definitely cover the [Reed-Solomon code](http://en.wikipedia.org/wiki/Reed_Solomon) which is integral to how compact discs work and [Huffman encoding](http://en.wikipedia.org/wiki/Huffman_encoding) which is used in JPEG, MP3, and ZIP file formats. Depending on the orientation of the course, you may also cover [Lempel-Ziv](http://en.wikipedia.org/wiki/Lempel_Ziv) which is used in the GIF format. Personally, I got Lempel-Ziv in an undergraduate algorithms course, but I think that might be atypical.

> **Comments:**
> **username_18**: And I got a lecture on Huffman encoding as an undergrad, which was required for a project.  
> **username_10**: Huffman is in one of the first chapters of CLRS, so it should definitely qualify  

---

### Answer by username_14 on 2013-11-12. Score: 23

GNU grep is a command line tool for searching one or more input files for lines containing a match to a specified pattern. It is well-known that grep is very fast! Here's a quote from its author Mike Haertel (taken from here):
GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the
final letter of the target string, and uses a lookup table to tell it how far
ahead it can skip in the input whenever it finds a non-matching character.


---

### Answer by username_13 on 2013-11-12. Score: 20

More generally, the [Kanellakis prize](http://awards.acm.org/kanellakis/) is awarded by the ACM for precisely such theoretical discoveries that have had a major impact in practice.

the 2012 award is for [locality-sensitive hashing](http://awards.acm.org/press_releases/tech_awards_2012.pdf), which has become a go-to method for dimensionality reduction in data mining for near neighbor problems (and is relatively easy to teach - at least the algorithm itself)

> **Comments:**
> **username_0**: I think this is teachable but not widely taught.  
> **username_13**: Unfortunate, but true. However, variants of LSH (like the Count-min sketch and relatives) are beginning to appear in "large-data" or "data mining" courses. I teach bloom filters in my algorithms class, for example.  
> **username_15**: As a personal experience, LSH did not scale for us on an instance of a "big data" (100mln items).  
> **username_13**: @lynxoid that's a separate discussion/question :). There are enough examples of where it *does* work that I think it's relevant to this particular question.  

---

### Answer by username_10 on 2013-11-12. Score: 19

The [CountMin Sketch](http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf) and [Count Sketch](http://www.mathcs.emory.edu/~cheung/papers/StreamDB/Frequency-count/FrequentStream.pdf), from data streaming algorithms, are used in industrial systems for network traffic analysis and analysis of very large unstructured data. These are data structure that summarize the frequency of a huge number of items in a tiny amount of space. Of course they do that approximately, and the guarantee is that, with high probability, the frequency of any item is approximated to within an an $\varepsilon$-fraction of the total "mass" of all items (the mass is the first or second moment of the frequency vector). This is good enough to find "trending" items, which is what you need in a lot of applications.

Some examples of industrial uses of these data structures are:

* Google's [Sawzall](http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/archive/sawzall-sciprog.pdf) system for unstructured data analysis uses the Count Sketch to implement a 'most popular items' function
* AT&T's [Gigascope](http://www2.research.att.com/~divesh/meetings/mpds2003/schedule/spatscheck.pdf) "stream database" system for network traffic monitoring [implements](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.2012&rep=rep1&type=pdf) the CountMin sketch.
* Sprint's Continous Monitoring (CMON) system [implements](http://www.cs.rutgers.edu/~muthu/ss.pdf) CountMin.

Here is also a [site](https://sites.google.com/site/countminsketch/home) that collects information about applications of CountMin.

As far as teaching, I know that basic sketching techniques are taught at Princeton in undergraduate discrete math courses. I was taught the CountMin sketch in my first algorithms course. In any case, the analysis of CountMin is simpler than the analysis for almost any other randomized algorithm: it's a straightforward application of pairwise independence and Markov's inequality. If this is not standard material in most algorithms courses, I think it's for historical reasons.

> **Comments:**
> **username_0**: Great examples (though not quite core algo right now).  

---

### Answer by username_12 on 2013-11-13. Score: 18

In the last decade algorithms have been used to increase the number (and quality, I think?) of kidney transplants through various kidney donor matching programs. I've been having trouble finding the latest news on this, but here are at least a few pointers:

* As recently as 2007 the Alliance for Paired Donation was using an algorithm of [Abraham, Blum, and Sandholm](http://www.cs.cmu.edu/~avrim/Papers/ec150abraham.pdf). They may still be using it, but I couldn't find out by searching online. Although this algorithm is almost surely not covered in "standard" courses, it combines several fundamental ideas that surely are taught in such courses to provide a good enough algorithm for a problem that is, in general, NP-complete (a variant of Cycle Cover).
* The National Kidney Registry also uses some standard algorithms, including (at one point) CPLEX. This led to an actually performed [chain of transplants linking 60 people](http://www.nytimes.com/2012/02/19/health/lives-forever-linked-through-kidney-transplant-chain-124.html?pagewanted=all&_r=0).

This is one of my favorite examples not just of the success of algorithms, but of the importance of studying algorithms for NP-complete problems. They can *literally save lives*, and have already done so!

> **Comments:**
> **username_16**: Also, a simpler version of these algorithms is used to trade board games: http://okasaki.blogspot.co.uk/2008/03/what-heck-is-math-trade.html  

---

### Answer by username_17 on 2013-11-14. Score: 17

Viterbi's algorithm, which is still widely used in speech recognition and multiple other applications: <http://en.wikipedia.org/wiki/Viterbi_algorithm> The algorithm itself is basic dynamic programming.

From Wikipedia:
"The Viterbi algorithm was proposed by Andrew Viterbi in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links.[1] The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognition, speech synthesis, keyword spotting, computational linguistics, and bioinformatics. For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal."


---

### Answer by username_19 on 2013-11-12. Score: 14

1. A\* is used in many Personal Navigation Devices (aka GPS units)
2. A\* is very well defined, and has been implemented fairly straightforward.
3. A\* isn't entirely trivial, but it doesn't take a Ph.D. to understand it.

> **Comments:**
> **username_18**: A* is also frequently taught in game design. I don't _think_ modern 3D games generally use A* for NPC navigation, but 2D/isometric games, as well as older games, do make use of the algorithm.  
> **username_20**: @BrianS Do you know examples of pathfinding algorithms used in 3D games, specifically enemies NPCs in games (such as a shooter npc) I remember reading something like... dividing a map in hexagonal sectors and use that as the node, instead of squares, and that allowed a smoother movement.  
> **username_18**: @Goodwine, Sorry, I do not have any real-world examples of pathfinding algorithms in 3D games. My personal experience has been with "cube"-like environments (map made of cubes, which characters stand on -- basically 2D, despite 3D rendering) and dummy AIs used for testing player-characters against.  

---

### Answer by username_21 on 2013-11-12. Score: 13

Check out Jens Vygen's project BonnTools for Chip Design.
<http://www.or.uni-bonn.de/~vygen/projects.html>
I have heard some talks on this and also looked at some of their papers.
They use Raghavan-Thompson style randomized rounding as well as multiplicative weight update method for solving large-scale multicommodity flow LPs.
However, like any big project, they need to do some engineering as well but the methodology is very much based on well-known algorithms.

> **Comments:**
> **username_0**: I'll have a look but it doesn't sound like typical algorithms material.  
> **username_21**: Hmm, randomized rounding is typically taught in PhD level algorithms courses, no?  
> **username_22**: Why just randomized rounding? Sanjeev Arora, Elad Hazan and Satyen Kale think that even mulplicative weights update method is basic enough to be taught at UG level :) "We feel that our meta algorithm and its analysis are simple and useful enough that they should be viewed as a basic tool taught to all algorithms students together with divide-and-conquer, dynamic programming, random sampling, and the like."  (cf. http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf).  

---

### Answer by username_23 on 2013-11-13. Score: 12

Funny that I saw this question today and then coincidentally clicked [this link on the many uses of the Fourier Transform](http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-homer-simpsons-face).


---

### Answer by username_24 on 2013-11-13. Score: 11

I like this system for saving the maximum number of lives in the UK with kidney transplants, based on maximum matching algorithms: [Paired and Altruistic Kidney Donation](http://link.springer.com/chapter/10.1007/978-3-642-30850-5_24).
They match up people needing kidneys who have a non-matching friend/relative willing to donate, with other people in the same situation, in a maximal way. Then on donation day, all the donors donate at the same time, followed by a speedy transport of kidneys around the country to the recipients.


---

### Answer by username_25 on 2013-11-13. Score: 11

I'm rather surprised that with all the fancy algorithms above, nobody mentioned the venerable Lempel-Ziv family of compression algorithms (invented in 1977/78).

1. Those are used everywhere - text to image to stream processing. It is quite possible that LZ\* is a single most used algorithm family in existence.
2. Dictionary compression was a considerable breakthrough in compression theory and a stark departure from Shannon-Fano style approach.
3. The algorithms in the family are rather straightforward and easy to comprehend.

**Update**

Apparently it was mentioned briefly already.


---

### Answer by username_26 on 2013-11-13. Score: 11

[singular value decomposition](http://en.wikipedia.org/wiki/Singular_value_decomposition) (SVD) has a strong connection to statistical [factor analysis](http://en.wikipedia.org/wiki/Factor_analysis) or [principal components analysis](http://en.wikipedia.org/wiki/Principal_components_analysis) and is comprehensible within an undergraduate linear algebra or statistics class, and has many important theoretical properties. it also plays a role in image compression algorithms. it played a key element in the winning entries in the [$1M Netflix prize contest](http://en.wikipedia.org/wiki/Netflix_prize) (one of the worlds largest datamining competitions in history) and is now implemented on their site to predict user ratings. it is also known to be highly related to [Hebbian self-organizing neural networks](http://en.wikipedia.org/wiki/Hebbian_learning) which originate in biological theory.

there is some connection also to [gradient descent](http://en.wikipedia.org/wiki/Gradient_descent) which is used widely in [machine learning](http://en.wikipedia.org/wiki/Machine_learning) & [artificial neural networks](http://en.wikipedia.org/wiki/Artificial_neural_networks) and as a very universally applied optimization technique of which case [Newton's method](http://en.wikipedia.org/wiki/Newtons_method) is a basic 2d form. there is a gradient-descent algorithm for obtaining the SVD.


---

### Answer by username_15 on 2013-11-12. Score: 11

Finding a Eulerian path is at the base of the genome assembly -- a task commonly performed when working with full genomes (in bioinformatics, medicine, forensics, ecology).

**UPDATE** Forgot this obvious one: UPS, FedEx, USPS all have to solve large instances of Traveling Salesman Problem every night. Saves a lot of time and money for them to send the drivers on an optimal route.

**UPDATE2** Minimum feedback vertex set problem is used for deadlock resolution in many OSes.

> **Comments:**
> **username_27**: Are you sure TSP is the problem that the parcel delivery companies are trying to solve?  I thought a bigger practical challenge was knapsack and other kinds of packing problems.  
> **username_15**: The assignments for the drivers change every day (i.e. UPS guy doesn't need to visit the same house every day), so the routes have to be updated on a daily basis. It is not a pure TSP - there are additional constraints such as one-way streets, no U-turns, delivering packages on one side of the street, but not the other.  
> **username_15**: I'm sure packing is also important though.  

---

### Answer by username_26 on 2013-11-14. Score: 10

this relatively new book is worth considering as a complete/detailed answer to the question in convenient, extended/collected form and which could be used as supplemental material for an algorithms class. [some of these have already been mentioned; the strong overlap itself is notable.]

* [Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers](http://rads.stackoverflow.com/amzn/click/0691158193) by MacCormick

  + search engine indexing
  + Pagerank
  + public key cryptography
  + error correcting codes
  + pattern recognition
  + data compression
  + databases
  + digital signatures
  + computability theory
* another reference somewhat similar but more theoretical, [The Best of the 20th Century: Editors Name Top 10 Algorithms](http://www.siam.org/pdf/news/637.pdf) Cipra/SIAM.

  + Monte Carlo method
  + simplex algorithm
  + Krylov subspace iteration
  + decompositional matrix computation
  + Fortran compiler
  + QR matrix algorithm
  + quicksort
  + FFT
  + integer relation detection
  + fast multipole algorithm

> **Comments:**
> **username_26**: 2nd ref is originally from January/February 2000 issue of Computing in Science & Engineering, a joint publication of the American Institute of Physics and the IEEE Computer Society. compiled by guest editors Jack Dongarra of the University of Tennessee and Oak Ridge National Laboratory and Francis Sullivan of the Center for Computing Sciences at the Institute for Defense Analyses  

---

### Answer by username_34 on 2013-11-12. Score: 7

The [Knuth-Morris-Pratt](http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) string search is widely used, specific, and taught in undergrad / graduate CS.

> **Comments:**
> **username_0**: Would be good if you could point to a specific use.  Something like MS Word uses KMP.  

---

### Answer by username_28 on 2013-11-14. Score: 6

Thinking of very basic algorithms

1. Random number generators are found everywhere and specifically in all games.
2. Databases are composed of many algorithms, including B+, Hashes, priority queues, regular expression, criptography, sorting, etc... A friend of mine says SGBDs are at the top of the computing food chain.
3. Sort is used everywhere, for example in Excel. It is actually used all time in real life, but usually humans use ad-hoc algorithms
4. Parity bits are used all around
5. Huffman encoding is in compression and transmission software
6. Stacks (LIFO) are used everywhere. Inside programming languages, in CPUs, etc...

Nice to show they appearing in real life:

A. Many groups use a kind of covering tree algorithm to communicate, by dividing telephone lists in hierarchical way among people
B. Cars in a intersection usually use a round-robin algorithm (in a voluntary way)
C. Most places, as banks and hospital, organize their clientes in a FIFO algorithm

> **Comments:**
> **username_29**: Sorting isn't an algorithm. It's a task, i.e., something you wish to perform, for which you must design (or, in practice, choose) an algorithm.  
> **username_30**: These don't seem to be specific examples as requested in the question.  
> **username_31**: [SGBD == RDBMS](http://stackoverflow.com/questions/980813/what-does-sgbd-mean) FYI for those didn't know.  

---

### Answer by username_32 on 2013-11-14. Score: 6

A fascinating algorithmic problem arises in medical application of CT scan. In Computed Tomography (CT), the body is exposed to X-rays from different angles. At one end of the scanner are the X-ray transmitters and at the other end the sensors. From such a series of scans, an image is reconstructed for the physician to examine!

The [filtered back projection](http://shaidekel.tripod.com/Lesson3.pdf)
algorithm is the basis for reconstruction of an image from a set of scans. This algorithm is actually a form of an approximation problem in which the "signal" is sampled below Nyquist rate. This algorithm is in use "behind the scenes" at all hospitals and the basic filtered back projection utilizes undergraduate math such as Fourier transforms to achieve the [Fourier Slice Theorem](http://en.wikipedia.org/wiki/Projection-slice_theorem).


---

### Answer by username_33 on 2013-11-15. Score: 6

An example of FFT

I once helped port an FFT algorithm to a different system language.

The algorithm was being used to determine line breaks in coaxial delivery of cable tv/internet/phone. Basically a technician would request a signal to be sent to the customer's box, at the same time they would pull up a real-time display of the statistics for the specific customer, such as QoS, dB, .... The technician could use the data and a graph to determine within a few feet between the house and pole where a partial break existed (or multiple breaks as I was told).

As mentioned above FFT is widely used, but this was one of the more blatant and obvious (in terms of why and how) I have seen in practice.

Sorry I had to keep it a high level.


---

### Answer by username_36 on 2013-11-13. Score: 5

Bresenham's line algorithm is the single most useful algorithm I've come across. Easy to understand Ive used it for lots of applications from line drawing to a complex spliner for 3d casting engine to a complex polygon renderer, as well as for complex animation and scaling uses.


---

### Answer by username_35 on 2013-11-24. Score: 4

**Customizable Route Planning** (Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck) <http://research.microsoft.com/apps/pubs/default.aspx?id=145688>

powers Bing Maps: <http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx>


---

### Answer by username_37 on 2013-11-13. Score: 2

Wikipedia has a decent collection of algorithms/applications classified more or less in a [list](http://en.wikipedia.org/wiki/List_of_important_publications_in_computer_science).
Microsoft provides the [top cited papers](http://academic.research.microsoft.com/RankList?entitytype=1&topDomainID=2&subDomainID=0&last=0&start=1&end=100) but without any explicit explanation of the area of computer science nor the application. There is also a chronological list from different CS conferences \_http://jeffhuang.com/best\_paper\_awards.html\_ compiled by Prof. Huang.

*Spectral Clustering* is an elegant clustering algorithm, known being *Normalized cuts* algorithm introduced by Jianbo Shi and Jitendra Malik for image segmentation. It has also well been developed in Data clustering applications, being an good intersection between the two communities.


---

### Answer by username_26 on 2013-11-14. Score: -2

two other personal favorite examples firmly rooted in computer science but maybe easily overlooked by abstractionist theoreticians, which have undergone enormous/transformative advances and had major-to-massive practical/applied impact in daily life over the last few decades. already an entire generation has grown up not knowing the world without them. basically the category of [Modelling and simulation](http://en.wikipedia.org/wiki/Modeling_and_simulation).

* [physics simulation algorithms](http://en.wikipedia.org/wiki/Dynamical_simulation). mainly using Newtons laws but using other laws (such as fluid dynamics). used in a wide variety of applications ranging from engineering applications, video games, and sometimes movies. this is responsible also for significantly improving safety, efficiency, or reliability of eg cars & airplanes via subjecting virtual/test designs to simulated stresses. a major related ongoing research area from bioinformatics with massive implications in biology eg drug design, disease prevention etc: [protein folding/structure prediction](http://en.wikipedia.org/wiki/Protein_structure_prediction). also note this years Nobel Prize in Chemistry was awarded for [chemistry simulation](http://www.nytimes.com/2013/10/10/science/three-researchers-win-nobel-prize-in-chemistry.html) to Karplus, Levitt, Warshel. physics simulation algorithms are highly involved in [nuclear weapons safety/testing](http://www.state.gov/t/avc/rls/202014.htm) eg at Los Alamos laboratories.
* [raytracing/CGI algorithms](http://en.wikipedia.org/wiki/Raytracing). this started out as a research topic merely a few decades ago [a friend got his masters degree in CS writing raytracing algorithms] but became very applied in eg games and the movie making business, reaching extraordinary levels of verisimilitude that is responsible for large amounts of special effects in movies. these industries have literally *billions of dollars* invested and riding on these algorithms and entire large corporations are based on harnessing them, eg [Pixar](http://en.wikipedia.org/wiki/Pixar). mostly initially used in eg scifi movies, the technique is now so widespread it is routinely used even in "typical" movies. for example recently [The Great Gatsby](http://www.imdb.com/title/tt1343092/?ref_=nv_sr_1) relied heavily on CGI effects to draw convincing or stylized environments, retouch the film/characters, etc.


---

### Answer by username_38 on 2013-11-24. Score: -3

Rosetta Code lists applied algorithms by [Programming Task](http://rosettacode.org/wiki/Category%3aProgramming_Tasks) (692) and by [Programming Language](http://rosettacode.org/wiki/Category%3aProgramming_Languages) (518) with Semantic MediaWiki.

> **Comments:**
> **username_29**: How is this an example of "core algorithms... deployed in commercial, governmental, or widely-used software/hardware"?  
> **username_38**: It would be useful to cross-reference the implementations of each of the excellent algorithms listed in other answers here to Wikipedia/DBpedia URIs. There aren't Wikipedia/DBpedia URIs for all of these algorithms; but there are Rosetta Code pages.  
> **username_38**: http://bigocheatsheet.com/ also lists Big-O complexity and links to Wikipedia articles for quite a few algorithms.  
> **username_29**: The question asks for examples of core algorithms used in significant pieces of software.  "Here's a website with algorithms implemented in a million languages" doesn't answer that question at all. In fact, it's the exact opposite of what the question is looking for.  
> **username_38**: A useful, contextually relevant reference nonetheless.  

---

### Answer by username_26 on 2013-11-16. Score: -5

maybe all the major/preferred algorithms of interest to this audience have been mentioned at this point. however, a few more deserve mention for completeness. & some analysis of what is considered a significant algorithm is relevant here.

in CS & IT fields there seems to be a phenomenon noticed long ago in AI called ["moving the goalposts"](http://en.wikipedia.org/wiki/Moving_the_goalpost). this is a psychological phenomenon where the field advances relatively quickly but people quickly mentally adjust to "the new normal" and take real or even breakthrough advances as mundane or unremarkable in retrospect, after accomplished, ie downplayed or minimized. this is highly captured in this question in the way that algorithms move from R&D into "deployment". quoting the author of the question in later comments:

> In fact, a negligible fraction of all the code that gets written is implementing anything that is interesting from an algorithmic point of view.

but this is problematic and basically a TCS-centric redefinition of the word "algorithm". presumably the interesting algorithms are advanced. does that mean that if a problem is reduced to an advanced algorithm, its no longer "interesting"? and "advanced" is clearly a moving target. so there is a way to define "algorithms" *narrowly*, or *broadly*. it seems the TCS definition changes on context, but note even in TCS, there is a trend toward the *broad* definition eg in the so-called ["algorithmic lens"](http://lazowska.cs.washington.edu/fcrc/Christos.FCRC.pdf).

sometimes the most ubiquitous algorithms are also the most overlooked! the internet and WWW is a large environment/near-ecology for algorithms. still relatively young at only about 2 decades old (invented ~1991) it has grown massively and exponentially in a short amount of time. WWW site growth has probably even outpaced the famous exponential Moores law.

the internet/WWW are supported by many sophisticated algorithms. the internet has complex routing algorithms built into routers (again powering multi-billion-dollar corporations such as Cisco). some advanced theory is applicable there eg in [routing algorithms](http://en.wikipedia.org/wiki/Routing). these algorithms were a subject of emerging, advanced/cutting edge research decades ago however a now so finetuned & well understood that its somewhat invisible.

we should not so soon forget that decades ago, leading researchers were not even sure if the internet world work or was possible (seen in early packet switching research, a radical new design pattern at the time departing from the prior circuit-switching), and even a few years ago there were fears that it would fail to scale at some point and begin to fail due to overwhelming spikes in volume.

it also uses sophisticated [error detection/correction](http://en.wikipedia.org/wiki/Error_correction). the internet probably *the* largest, most [fault-tolerant](http://en.wikipedia.org/wiki/Fault_tolerance) system ever built by humans, still growing.

next, there is a strong case to make that the algorithms powering the WWW are advanced. [HTTP](http://en.wikipedia.org/wiki/Http) & web servers are highly tuned/optimized and also use advanced security/encryption protocols (HTTPS). the rendering logic of a web page has become extremely advanced in [HTML5](http://en.wikipedia.org/wiki/Html5) & [CSS3](http://en.wikipedia.org/wiki/Css), along with the [Javascript](http://en.wikipedia.org/wiki/Javascript) programming language.

the relatively new CSS has various principles similar to [OOP programming](http://en.wikipedia.org/wiki/Object_oriented_programming) such as reusability and inheritance. speaking of typesetting, [TeX](http://en.wikipedia.org/wiki/TeX) is an important, internally complex scientific typesetting system (not so different than a programming language) invented by Knuth that can now be rendered on web pages (and is used in possibly hundreds of thousands of scientific papers or more).

another relatively new area of algorithms building on the internet, still emerging, those based on [collective intelligence](http://en.wikipedia.org/wiki/Collective_intelligence). stackexchange software itself is an example of a sophisticated collective intelligence system. [social networking](http://en.wikipedia.org/wiki/Social_networking) also exhibits the key features of collective intelligence and features are continually being added to increase that intelligence (for example facebook "Likes" are only a few years old). the field of rating systems is based on [collaborative filtering](http://en.wikipedia.org/wiki/Collaborative_filtering) algorithms and is still evolving based on new research and applications.

so in short, all *revolutionary successes transforming daily human experience* actually quite far beyond merely "field goals". as the title of the question states, all *core algorithms deployed*. now so ubiquitous and invisible as to be something like the IT expression, "part of the plumbing".

> **Comments:**
> **username_26**: many citations could be added to this. here is one to start: [DARPA and the internet revolution](http://www.darpa.mil/WorkArea/DownloadAsset.aspx@id=2554.pdf) by Waldrop  
> **username_26**: another ref on internet optimization, [biography of Danny Lewin](http://en.wikipedia.org/wiki/Citation_analysis), cofounder of akamai, "the genius who transformed the internet"  

---

### Answer by username_39 on 2013-11-13. Score: -8

An amazingly successful (hardware) algorithm is the power-on reset.

Without a system whereby a computer is in a known state when power is applied, **nothing else happens right**.

Power-on reset is why anything works at all that has a CPU in it, whether considered embedded or otherwise.

Next time you're at the watering hole for programmers and computer scientists, raise your glass of cherry soda to the power-on reset.

> **Comments:**
> **username_29**: Power-on reset isn't an algorithm. It's a task, i.e., something you wish to perform, for which you must design an algorithm.  

---

