# Tag Info

## Hot answers tagged application-of-theory

478

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

40

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

34

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

30

As I understand it, the National Resident Matching Program was for a long time just a straight application of the Gale-Shapley algorithm 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...

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 which is integral to how compact discs work and Huffman encoding which is used in JPEG, MP3, and ZIP file formats. Depending on the orientation of the course, ...

23

I am one of the authors of the paper linked above. Just want to mention that we used state-of-the-art'' to mean algorithms (with publicly available implementations) that perform well on max-flow instances arising in computer vision. I would also like to add that within that narrow (yet practical) context, often the algorithms that perform well are the ...

22

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

19

More generally, the Kanellakis prize 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, 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 ...

18

The CountMin Sketch and Count Sketch, 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 ...

17

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

17

Interestingly, there is a nascent mathematisation of version control systems, although at this point it's only partially applicable to Git. It's called patch theory [1, 2, 3, 4, 5] and arose in the context of the DARCS version control system. It can be seen as an abstract theory of branching and merging. Recently patch theory has been given HoTT [ 6 ] and ...

16

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

16

A git repository can be thought of as a partially ordered set of revisions (where one revision is earlier than another in the order if it is a direct or indirect successor of the earlier one). The partial orders that you get from git repositories tend to have low width (the size of the largest set of mutually independent revisions) because the width is ...

13

I see two separate directions to take your question. One is How has a computer science philosophy and computational thinking impacted the field of economics, and why should economists care about the computer science approach? This is a really cool but really broad question that I'll avoid attempting to address. The second is more specific: Now that computer ...

13

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

12

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

11

Habib and Paul did a great survey on the algorithmic applications of graph modular decomposition. In our recent result that shows parameterized tractability of INTERVAL DELETION problem (to remove at most $k$ vertices from the give graph to make it into an interval graph), graph modular decomposition does plays an important role. This problem does receive a ...

11

Funny that I saw this question today and then coincidentally clicked this link on the many uses of the Fourier Transform.

10

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

10

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). 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. Dictionary compression was a considerable ...

10

singular value decomposition (SVD) has a strong connection to statistical factor analysis or 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 $... 10 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. 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 ... 9 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 ... 8 Main stream game theorists are, I think, becoming much more open to contemporary work in the computer science community, so it may be less necessary to "make the case'' for algorithmic game theory than it has been in the past. One of the texts that I know of that is most accessible to auction theorists with an economics background is Jason Hartline's "... 8 there are several ways to answer this question but not necessarily a consensus answer. generally algorithms that have been implemented and released for public distribution are "practical". however, some algorithms that have been devised but not yet implemented may be practical but "the jury is out" on them so to speak.** a good strategy for practical ... 8 Simulating quantum systems! I noticed that in the other answer that mentioned this there were several comments about whether this was true since it is a non-obvious claim. And people requested references. Here are some references. Original proposal by Feynman: Feynman, R.: Simulating physics with computers. Int. J. Theor. Phys. 21(6) (1982) 467–488 ... 8 Kirk Pruhs is a leader in the area of "green computing", the study of algorithms that treat energy as an expensive resource. Take a look at these slides and this survey by Sandy Irani and Pruhs. 8 One family of results not mentioned in the excellent references of @Marzio's answer is relations between the isoperimetric (Dehn) function of a group$G$and the nondeterministic time complexity of the word problem in$G$. For example: For finitely generated groups$G$,$WP(G) \in \mathsf{NP}$if and only if$G$can be embedded in a finitely presented group ... 8 There are lots of overlaps between small world and scale-free, but I think much less so between those two and expanders. The terms "small world" and "scale-free" are often used informally, but formal definitions are often along the lines of: Small-world means short average (or maximum) path length (typically$O(\log n)$, with$n\$ vertices) and highly ...

8

One application involves stripification of triangle meshes in computer graphics — a Hamiltonian path through the dual graph of the mesh (a graph with a vertex per triangle and an edge when two triangles share an edge) can be a helpful way to organize data and reduce communication costs.

Only top voted, non community-wiki answers of a minimum length are eligible