Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

31–40 of 507 posts

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

#33

Post by skrebbel »

phamilton wrote: post #4

I like Dijkstra's algorithm for finding the shortest path between two nodes in a graph. It's not so much that it is "beautiful", but it is a remarkably simple algorithm that a human can follow manually. The reason it is efficient is easily understood (it's easy to see how we are able to "finalize" nodes because it's obvious there is no shorter path to that node), and it takes what would otherwise be a complicated tas…

I've always suspected that Dijkstra's shortest path algorithm was invented many times before he wrote it down. The algorithm itself is relatively straight forward and I can imagine that a competent programmer not aware of it could come up with it independently.

I mean, even Dijkstra himself came up with it because he needed it for a telecom gig. He can't have been the first one in the world who needed to find the shortest path in a graph. He just also happened to be a scientist, experienced in the whole "how to publish a paper" thing.

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

#37

Post by kamaal »

Not exactly an algorithm, but I like recursion as a pattern to be just insane to even think about.

You can build an entire working structure from base operations, exit conditions and logic that scale to higher states of the operations.

Extending the same, TCO is another very elegant concept in CS.

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

#38

Post by narag »

B Trees. You can call them a set of algorithms or a data structure if you prefer, but its core idea can be expressed as an algorithm: making the root of the tree emerge from leaves. It's kind of democratic!

Edit: it's also a massively practic idea that powers most databases.

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

#39

Post by carapace »

Dancing Links (Knuth's paper: https://arxiv.org/pdf/cs/0011047.pdf )

> In computer science, dancing links is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.

~ https://en.wikipedia.org/wiki/Dancing_Links

Also SEQUITUR http://www.sequitur.info/

> Sequitur (or Nevill-Manning algorithm) is a recursive algorithm developed by Craig Nevill-Manning and Ian H. Witten in 1997[1] that infers a hierarchical structure (context-free grammar) from a sequence of discrete symbols. The algorithm operates in linear space and time. It can be used in data compression software applications.

~ https://en.wikipedia.org/wiki/Sequitur_algorithm

Part of the reason I like these both is that they each require sharp pointer manipulation to work efficiently.

I'm a functional programming fan, these beautiful and useful algorithms remind me that purity isn't everything, eh? Also, it's fun to think about how you might get FP code to emit correct pointer-munging code for them.

Post reply on HN