Ask HN: What are your favorite algorithms?

#1

Post by EFruit » Sun, Jan 29, 2017, 11:53 PM UTC

Post any algorithms you think are cool, inventive, or useful. PDF links or blog posts are appreciated.

My current favorite is SWIM. https://www.cs.cornell.edu/~asdas/research/dsn02-swim.pdf

Re: Ask HN: What are your favorite algorithms?

#2

Post by gjvc » Mon, Jan 30, 2017, 12:24 AM UTC

Great question. Without a doubt, my favourite is the Burrows-Wheeler transform (as used by bzip2)

#3

Post by zelah » Mon, Jan 30, 2017, 12:49 AM UTC

Parallelizable and efficient method for producing high quality pseudo random bits.

Designed to achieve maximal period (with 500 bit state the period of repetition is one less than 2^500).

Can be run backwards or forwards. Running it backwards undoes running it forwards and reproduces the pseudo random bits in reverse order.

#4

Post by notforgot » Mon, Jan 30, 2017, 1:31 AM UTC

It looks like SWIM scales better than Raft. Are there well-known production systems that use it?

#5

Post by NTDF9 » Mon, Jan 30, 2017, 1:54 AM UTC

A modified version of it is used in most CPU register out-of-order execution

#6

Post by ewwertee2454 » Mon, Jan 30, 2017, 4:06 AM UTC

Metropolis-Hastings:

#7

Post by kul_ » Mon, Jan 30, 2017, 4:41 AM UTC

I have never seen anything more elegant than Disjoint Set Datastructure https://en.wikipedia.org/wiki/Disjoint-set_data_structure

#8

Post by Mr_P » Mon, Jan 30, 2017, 5:06 AM UTC

Simplex. If you can transform your NP hard optimization problem into an LP, simplex can often work like magic.

#9

Post by jnpatel » Mon, Jan 30, 2017, 5:10 AM UTC

#10

Post by daurnimator » Mon, Jan 30, 2017, 5:15 AM UTC

The burrows-wheeler transform is pretty interesting https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf.... It's behind the bzip compression format.