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

The "FRAIG" algorithm is pretty cool. To find equivalent nodes in an And/Inverter graph (e.g., a hardware circuit), it operates by... (1) simulating the graph on random numbers to identify nodes that might be equivalent (this can be done with huge parallelism by using wide, bitwise and/not operations) (2) using SAT to determine if these candidates really are equivalent (3) building a new network that canonicalizes all of the nodes you've found to be equivalent.

It can be a really effective pre-processing step for many kinds of circuit analysis.

https://people.eecs.berkeley.edu/~alanmi/courses/2005_290A/p...

>do it one pass in O(n) time

Mind you, the “n” here is not the number of nodes!

More precisely, Dijkstra’s algorithm runs in O(E + V * log V) time (if the priority queue is implemented with a heap), where E is the number of edges and V is the number of nodes.

In the general case, E = O(V^2) (i.e. fully connected graph), so Dijkstra’s algorithm can calculate the shortest path to V nodes in O(V^2) time. It sounds less staggering this way.

And in a general graph where negative edge-weights are permitted, it’s actually impossible to find the shortest path between two nodes without finding the shortest path between the source node and every other node! It’s pretty easy to see why: you can’t be sure you’ve actually found the shortest path until you’ve covered all the edges, because there’s always the possibility of a very large negative edge to be visited.

Dijkstra’s algorithm improves on this general case by exploiting the fact that the edges must have positive weight.

Apirori algorithm for finding frequently occurring subsets in a set of sets of objects. I find the algorithm beautiful because:

1) It takes advantage of a simple insight: all frequent subsets must be unions of other subsets that are at least as frequent.

2) It uses a Trie data structure in a very beautiful way, traversing it in-order while searching for elements from a lexically sorted list of lexically sorted lists.

Floyd's Tortoise and Hare is pretty fun: https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoi...