# Tag Info

487

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

41

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

33

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

23

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

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

15

I won't say it is impossible, but to me it seems... challenging at best. Social science deals with the behavior of humans, and humans are complex. TCS deals with mathematics and computer algorithms, which can be precisely and rigorously modelled. Those two don't seem well-matched to me. My suspicion is that it will be difficult to apply techniques from ...

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

12

There are some interdisciplinary areas in CS that may be similar to what you're looking for. These areas are often considered "applied", in the sense that they restrict their research to a certain application domain of CS and the relevance of results is mainly measured by the impact of the result on the application domain. However, these areas are ...

11

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

11

Yes, absolutely! This is a blossoming new field in the social sciences that a lot of people are excited about right now. The phrase to look for is "computational social science". There is a a lot of work in graph theory and networks in particular. Some researchers to look into are: Mark Newman Aaron Clauset Nicholas Christakis (Also see the ...

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

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

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 ... 9 Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap. What you could hope for is good vertex/edge expansion for sufficiently large sets. However, if you have tightly-knit communities within the network, then again you would expect low expansion. I'm ... 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.

7

The Knuth-Morris-Pratt string search is widely used, specific, and taught in undergrad / graduate CS.

7

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis. It therefore seems hard to justify to practitioners. Proving bounds for the worst case is often easier than proving bounds for even "nice" definitions of average case. Asymptotic analysis is also often much ...

7

I think that you can start (and probably end, because it's a huge list :-) with the references in the recent Charles F. Miller's paper: "Turing machines to word problems" (2013). And another recent paper that surveys the connections between group theory and theory of automata and formal languages and hase a huge (>100 entries) reference section is: Tullio ...

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