Ask HN: What's your favorite elegant/beautiful algorithm? • Hacker News Board

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#21

Post by aportnoy » Wed, Oct 17, 2018, 6:23 AM UTC

Any dynamic programming algorithm.

Heap sort using an array impressed me as an undergrad.

FFT continues to amaze me as a scientific programmer.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#22

Post by antipaul » Wed, Oct 17, 2018, 6:24 AM UTC

I’ll mention not a CS algorithm but a machine learning algorithm: random forest.

I love the idea of adding not _structure_ but _randomness_, in order to better find a solution to some problem.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#23

Post by pg_bot » Wed, Oct 17, 2018, 6:27 AM UTC

The simplex algorithm

https://en.wikipedia.org/wiki/Simplex_algorithm

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#24

Post by iMuse » Wed, Oct 17, 2018, 6:28 AM UTC

When learning to analyse algorithms, I found Kruskal's and Dijkstra's algorithms very interesting.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#25

Post by pimmen » Wed, Oct 17, 2018, 6:29 AM UTC

This is like choosing your favorite friend, I love a lot of algorithm's in their own, special way. I could also answer in families of algorithms, but that would be cheating. Some of my favorites have already been mentioned, too.

So, I'll mention Monte Carlo integration. It's very simple to implement, it was one of the first tasks my first CS professor gave freshman students, and he did it for the same reason I love it; it gives such profound insights about how computers can solve complex mathematical problems humans can't. I shiver every time I solve a problem with a Monte Carlo method.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#26

Post by w1nt3rmu4e » Wed, Oct 17, 2018, 6:29 AM UTC

I may be stretching the definition of algorithm here, but I've always been fascinated by signed distance functions / signed distance fields for 2D / 3D shapes.

Being able to do the full set of boolean operations on shapes with just `min` and `max` operations is pretty cool. Doubly so because boolean operations on standard geometry is such a difficult, messy problem.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#27

Post by Maro » Wed, Oct 17, 2018, 6:29 AM UTC

https://en.wikipedia.org/wiki/Paxos_(computer_science)

It took me days/weeks of processing to understand it (and appreciciate the problem(s) it solves).

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#28

Post by Voltage » Wed, Oct 17, 2018, 6:30 AM UTC

In graphics.... I'm a fan of - Sphere tracing distance fields (Ray marching distance fields)

and

- Marching Cubes

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#29

Post by geoah » Wed, Oct 17, 2018, 6:32 AM UTC

Fast inverse square root, sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates 1/√x, the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number x in IEEE 754 floating-point format.

https://en.m.wikipedia.org/wiki/Fast_inverse_square_root

I especially love the story around it.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#30

Post by btschaegg » Wed, Oct 17, 2018, 6:35 AM UTC

From a pure algorithm perspective: Buzhash. It's extremely simple and elegant (it mainly builds on the reversibility of XOR) and extremely fast. Used e.g. in Attic/BorgBackup for data deduplication.

For data structures: Either Hash Array Mapped Tries (HAMT; used in most immutable data structures) or Log-structured Merge Trees (LSM-Trees; an important concept for databases, mainly very useful because random access on "spinning rust" is very slow).