Skip
# Which algorithms changed the world?

Post

# Which algorithms changed the world?

August 10, 2014 2:50 PM Subscribe

A recent post to the blue proposed a set of equations that changed the word. As a computer professional, I'm curious, which algorithms transformed the world?

I'm not necessarily looking for 'algorithms a computer programmer should know' or 'algorithms we should teach in CS 101.' An algorithm impact on the world should be the primary criteria, rather than pracitioner familiarity or pedagogical use.

I'm not necessarily looking for 'algorithms a computer programmer should know' or 'algorithms we should teach in CS 101.' An algorithm impact on the world should be the primary criteria, rather than pracitioner familiarity or pedagogical use.

With no better criteria than what immediately comes to mind:

posted by straw at 3:09 PM on August 10, 2014 [3 favorites]

- Either arithmetic or Huffman encoding for data compression. I think you could make an argument for Lempel–Ziv here too, but Huffman & arithmetic encoding both start to think about data as something other than fixed length.
- Public key encryption. Because holy crap.
- Map-Reduce. Because thinking about big data sets changed.
- Ray tracing. Because it pushed all sorts of thinking about "how can you get this result, but efficiently". I would suggest that from turning this on its head we get things like Warnock's algorithm, REYES, the raycasting renderers of the '90s, and from exploring it we get implicit surfaces and more. Related: Stochastic sampling in graphics.
- Bezier curves, Bresenham's line algorithm, and I'm probably short-changing a bunch of other graphics primitives ideas. For similar reasons.
- B-Trees.

posted by straw at 3:09 PM on August 10, 2014 [3 favorites]

A fast inverse square root function has been the subject of a lot of discussion, and it has contributed to the creation of realistic 3D environments.

posted by SpacemanStix at 3:15 PM on August 10, 2014

posted by SpacemanStix at 3:15 PM on August 10, 2014

PageRank revolutionized searchability, and ultimately made the Worldwide Web's explosive growth usable.

posted by jackbishop at 3:19 PM on August 10, 2014 [2 favorites]

posted by jackbishop at 3:19 PM on August 10, 2014 [2 favorites]

Top 10 Algorithms of the 20th Century

Top 10 Algorithms in Data Mining

posted by un petit cadeau at 3:56 PM on August 10, 2014

Top 10 Algorithms in Data Mining

posted by un petit cadeau at 3:56 PM on August 10, 2014

Forward Error Correction (AKA "Hamming Code")

posted by Chocolate Pickle at 4:06 PM on August 10, 2014 [2 favorites]

posted by Chocolate Pickle at 4:06 PM on August 10, 2014 [2 favorites]

Also, time sharing about 50 years ago.

And symmetric multiprocessing about 20 years ago.

posted by Chocolate Pickle at 4:10 PM on August 10, 2014

And symmetric multiprocessing about 20 years ago.

posted by Chocolate Pickle at 4:10 PM on August 10, 2014

The Genetic algorithm. This is used to solve all kinds of optimization problems which can't be solved any other way in practical time. Genetic algorthms don't necessarily find

posted by Chocolate Pickle at 4:14 PM on August 10, 2014 [2 favorites]

*the*best answer but they nearly always find*almost the best*answer, in hours or days instead of in millions of years.posted by Chocolate Pickle at 4:14 PM on August 10, 2014 [2 favorites]

Quicksort.

Discrete Cosine Transform (aka, JPEG encoding).

posted by plinth at 4:36 PM on August 10, 2014

Discrete Cosine Transform (aka, JPEG encoding).

posted by plinth at 4:36 PM on August 10, 2014

Simplex algorithm for solving linear programs.

posted by SemiSalt at 4:41 PM on August 10, 2014 [1 favorite]

posted by SemiSalt at 4:41 PM on August 10, 2014 [1 favorite]

Internet routing algorithm?

TCP algorithm for reliable communication over an unreliable channel?

posted by rustcrumb at 5:26 PM on August 10, 2014

TCP algorithm for reliable communication over an unreliable channel?

posted by rustcrumb at 5:26 PM on August 10, 2014

Carrier sense multiple access with collision detection, aka Ethernet.

IP forwarding algorithm, the Internet Protocol

These two are why you can just plug one more machine into a computer network, and it all works without having to reconfigure everything else on the network. [This probably doesn't seem so amazing if you never had to set up a network in the 1990s.]

posted by benito.strauss at 6:39 PM on August 10, 2014

IP forwarding algorithm, the Internet Protocol

These two are why you can just plug one more machine into a computer network, and it all works without having to reconfigure everything else on the network. [This probably doesn't seem so amazing if you never had to set up a network in the 1990s.]

posted by benito.strauss at 6:39 PM on August 10, 2014

Diffie-Helleman key exchange. Transmitting secure information over an insecure channel. Flat out genius.

posted by It's Never Lurgi at 6:39 PM on August 10, 2014 [2 favorites]

posted by It's Never Lurgi at 6:39 PM on August 10, 2014 [2 favorites]

Embarassingly, that title belongs to Ralph Merkle, although Diffie and Helleman devised the first practical algorithm. It amazes me that anyone was crazy enough to come up with something so obviously impossible.

posted by It's Never Lurgi at 7:13 PM on August 10, 2014 [1 favorite]

posted by It's Never Lurgi at 7:13 PM on August 10, 2014 [1 favorite]

Ulam's Montecarlo method, for sure. Especially as he came up with it when recuperating from meningitis and wasn't supposed to be thinking very hard, so played a lot of solitaire and got wondering about the probabilities of winning …

posted by scruss at 7:26 PM on August 10, 2014

posted by scruss at 7:26 PM on August 10, 2014

FFT.

The Fast Fourier Transform made the nuclear test ban treaty possible. Without it, computers could not process seismic data fast enough to determine (a) whether a particular set of tremors was a nuclear bomb or not and (b) where the tremors originated.

posted by pmb at 8:14 PM on August 10, 2014 [3 favorites]

The Fast Fourier Transform made the nuclear test ban treaty possible. Without it, computers could not process seismic data fast enough to determine (a) whether a particular set of tremors was a nuclear bomb or not and (b) where the tremors originated.

posted by pmb at 8:14 PM on August 10, 2014 [3 favorites]

The Smith-Waterman algorithm for sequence alignment has had an enormous impact on biomedical research (think human genome project and everything spawned from it).

posted by chrisamiller at 10:31 PM on August 10, 2014

posted by chrisamiller at 10:31 PM on August 10, 2014

The perceptron algorithm -- gave rise to neural networks, SVMs, and the general industry of supervised classification that drives most of AI and data analysis today.

Algorithms to do linear regression gave rise to the quantitative social and biomedical sciences.

posted by redlines at 5:24 AM on August 11, 2014

Algorithms to do linear regression gave rise to the quantitative social and biomedical sciences.

posted by redlines at 5:24 AM on August 11, 2014

Ada Lovelace's "Note G" algorithm for generating Bernoulli numbers. It is arguably the very first computer program.

posted by kyrademon at 8:48 AM on August 11, 2014 [1 favorite]

posted by kyrademon at 8:48 AM on August 11, 2014 [1 favorite]

The least squares method for finding a line that fits a set of data points (discovered by Gauss). It was originally used to determine the path of comets and asteroids.

posted by A dead Quaker at 5:04 AM on August 19, 2014

posted by A dead Quaker at 5:04 AM on August 19, 2014

Kalman Filtering, which led to GPS and most modern guidance systems (from satellites to missiles, and I strongly suspect Google's car uses it), and has an absolutely eery ability to strip noise from signal at jaw-dropping rates.

posted by IAmBroom at 8:47 AM on November 2, 2014

posted by IAmBroom at 8:47 AM on November 2, 2014

You are not logged in, either login or create an account to post comments

posted by BungaDunga at 2:57 PM on August 10, 2014 [10 favorites]