HN Explorer

Ask HN: What are your favorite algorithms?

163 points by EFruit ↗ HN
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

92 comments

[ 2.9 ms ] story [ 181 ms ] thread
zelah
Linear Hybrid Cellular Automata: https://pdfs.semanticscholar.org/7835/161f253ab117a3666fa8e7...

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.

notforgot
It looks like SWIM scales better than Raft. Are there well-known production systems that use it?
[deleted]
(comment deleted)
cube2222
SWIM is in no way an alternative to Raft, and vice-versa. SWIM is a membership algorithm, Raft is a consensus algorithm. They are often used together. (a SWIM alternative is plain Gossip and a Raft alternative is Paxos)
kul_
I have never seen anything more elegant than Disjoint Set Datastructure https://en.wikipedia.org/wiki/Disjoint-set_data_structure
gpderetta
Another fan of union-find here as well. Simple, elegant and magical.

Also best (only?) practical use of the (inverse) Ackermann function!

aryamaan
+1. I was in love with union data structure as well when I get to know about them. And always used to feel good when I used to solve any algo problem with it.
Mr_P
Simplex. If you can transform your NP hard optimization problem into an LP, simplex can often work like magic.
nhaehnle
If you can transform your NP hard optimization problem into an LP, you have proven P = NP because LPs can be solved in polynomial time.

That said, many combinatorial optimization problems that look quite similar to NP hard problems have very nice and efficient LP formulations, and for many NP hard problems, integer programming-based methods (which in the end mostly solve LP relaxations) are among the best algorithms. For example, planar TSP can be solved for tens or even hundreds of thousands of nodes using the LP relaxation, branch, and cut tool set.

Modern LP solvers don't just use the Simplex method though. I'm very partial to the Simplex method myself, but in practice, Interior Point Methods are often used.

110011
Adding to what you say, OP might have meant the use of LP solvers in branch and bound type algorithms to solve hard problems after recasting them as integer programs.
jnpatel
Bloom filters: https://en.wikipedia.org/wiki/Bloom_filter
jones1618
Agreed. Bloom filters are amazingly useful for checking membership in a set while taking much less space than a database or hash table. They achieve this by being crazily "probabilistic", sacrificing a small amount of accuracy for speed and compactness. Still, this sort of broken, degenerate hash table has found a ton of uses in everything from spell checkers to distributed content networks.
daurnimator
The burrows-wheeler transform is pretty interesting https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf.... It's behind the bzip compression format.
psi-squared
This is related to my current favourite algorithm: Because the BWT is closely related to the suffix tree of the original string, there's an algorithm to search for a substring of length 'm' in a BWT-ed string of length 'n' in O(m log n) time!

The one downside is that you have to pre-process the string, which takes O(n) time and between 5n and 9n space depending on exactly how you do it. But after that, you can do as many searches as you want practically "for free".

There's a paper outlining the various algorithms available here: (PDF) http://www.cosc.canterbury.ac.nz/research/reports/HonsReps/2...

pmalynin
Number Theoretic Transform aka Discrete Fourier Transform.

The algorithms for computing it are beautiful and have enabled much of the technology we see around us today.

pitaj
This. FFT is crazy awesome.
theemathas
The Fastest and Shortest Algorithm for All Well-Defined Problems: https://arxiv.org/abs/cs/0206022

Abstract: An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. M avoids Blum's speed-up theorem by ignoring programs without correctness proof. M has broader applicability and can be faster than Levin's universal search, the fastest method for inverting functions save for a large multiplicative constant. An extension of Kolmogorov complexity and two novel natural measures of function complexity are used to show that the most efficient program computing some function f is also among the shortest programs provably computing f.

The catch is that the constants in the big-O are enormous.

zelah
I vote twice for this one!
palashkulsh
Any laymen explanation ? Not able to grasp the concept.
[deleted]
(comment deleted)
theemathas
It does two things concurrently: (1) search for an algorithm along with proofs for its correctness and time upper bound (2) run the fastest algorithm found so far, possibly aborting an slower algorithm when a faster one is found.

Everything is scheduled so it's asymptotically optimal. However, there's an added cost to search for algorithms. This cost is exponential in the proof length, but constant for each problem since it is independent from the inputs. Of course, this constant is ridiculously huge.

AstralStorm
Funny thing is, you can offload most of this to compile time, which is what Isabelle is doing, but then you miss out on guaranteed optimal runtime. Also the proof database may not be complete anyway.
palashkulsh
@theemathas thanks, @pwdisswordfish - nice one :D
AstralStorm
It is only an existential proof, the algorithm has never been implemented. The closest that comes to it is the proof searcher in Isabelle. (blast method)
useanalias
Contrastive divergence for RBMs. Incredibly simple, but absolutely beautiful how it modifies the energy surface. Also, just in general a cool use of Gibbs sampling.
toomanybeersies
As basic as it is, and completely uninventive, I've always loved Dijkstra's algorithm.

It was probably the algorithm that cemented my love of computer science, it's such an elegant solution to a problem and so simple once you understand it.

taeric
Why "uninventive?"
samcal
I believe GP meant that picking Dijkstra's is an uninventive answer to the question of a favorite algorithm, since it's very well-known.
taeric
Ah that makes sense.
rak00n
I was always thought it was a greedy way of doing a breadth first search.
cperciva
I feel I have to mention the algorithm for matching with mismatches which I published in my thesis (http://www.daemonology.net/papers/thesis.pdf), simply because it gave me a legitimate opportunity to use the phrase "Fourier Transform of the FreeBSD kernel".
kovrik
HyperLogLog
110011
I also like the moral predecessor of this algorithm (Morris counting algo I think it's called) which solves the simpler problem of estimating the number of elements in a stream with loglog space. Curiously it appears as an exercise in CLRS.
CalChris
Someone already mentioned Tomosulo.

RSA.

taeric
Knuth's DLX algorithm. Uses what he calls dancing links to perform backtracking in basically constant space with a clever trick on doubly linked lists.

He recently updated his implementation. Is very fun to read his notes on his implementation. In particular, he discusses things he had wrong.

If you like poor JavaScript implementations, I can post mine again.

gwicks56
Diffie-Hellman

One of those algorithms where you go "Shit so obvious and also so completely genius that I could never have thought of it"

Also, the internet as we know it would not work without it