Ask HN: What are your favorite algorithms?
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
My current favorite is SWIM. https://www.cs.cornell.edu/~asdas/research/dsn02-swim.pdf
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.
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.
There's a way to do it in O(1) space, though.
If you start off two runners in the list, and each "step" move one twice and the other only once, if there's a loop they will eventually run into each other and be processing the same element. Simple, elegant, and nothing I'd have ever thought of. :)
The list node contains a pointer and some data, most likely another pointer, or a primitive type, or a struct of primitive types. Which means, that on all modern systems, a list node is aligned to at least 16 bits, much more likely 32 bits. That means that the pointer to the node always has the last bit set to zero. So:
bool containsCycle(node_t *root)
{
node_t *p = root;
bool ret = false;
if (!root) return false; // Empty list
while (p->next && !ret)
{
if ((uintptr_t)p->next & 1)
{
ret = true;
break;
}
node_t *q = p->next;
p->next = (uintptr_t)p->next | 1;
p = q;
}
// Reset all pointers
p = root;
while (p->next && ((uintptr_t)p->next & 1))
{
p->next = (uintptr_t)p->next & ~1;
p = p->next;
}
return ret;
}
So I beg to differ, it's not really "better" by any metric.
Tortoise and hare can only detect that a cycle exists. This hack will tell you exactly which node the cycle starts on. That means that if you want to e.g. repair a list, you can just cut that last link and set it to either null or root. Granted, this wasn't the original problem.
1 -> 2 -> 3 -> 4 -> 5 -> 6
^ |
|______________|
Step: 0 1 2 3 4
Tortoise: 1 2 3 4 5
Hare: 1 3 5 3 5 <- pointers reference same node, cycle exists
Step: 0 1 2
Tortoise: 5 6 3
Tortoise2: 1 2 3 <-cycle starts at 3 X(n+1) = (A * X(n) + B) mod C
https://visualgo.net/cyclefinding
Really cool!
Did have to remind myself to start the double-jumper off before the single-pointer to prevent a short-circuit, but that's a great solution to cyclical lists.
Where did you learn about this?
[1] https://en.wikipedia.org/wiki/LZ77_and_LZ78 [2] https://en.wikipedia.org/wiki/Rsync#Algorithm [3] https://en.wikipedia.org/wiki/Gift_wrapping_algorithm [4] https://en.wikipedia.org/wiki/XOR_linked_list
Do you mean the rolling checksum part?
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.
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...
Also best (only?) practical use of the (inverse) Ackermann function!
Whitted's recursive ray tracing algorithm https://en.wikipedia.org/wiki/Ray_tracing_(graphics)#Recursi...
PageRank
Search for the paper by Adam Kalai on how to generate random factorized integers easily. It uses log^2 n primality tests an average. The result is originally by Eric Bach who managed it using only log n primality tests but using a more complex algorithm.
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
PHP implementation: https://github.com/bandwidth-throttle/token-bucket
http://nginx.org/en/docs/http/ngx_http_limit_req_module.html
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.
A modified version of it is used in most CPU register out-of-order execution
https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...
[0] http://www.geeksforgeeks.org/fleurys-algorithm-for-printing-...
It shows the importance of making a good definition and thinking differently (for the run time analysis I thought for a while and failed to come up with an argument why it runs in linear time, but once you see it differently it's obvious :))
I only recently had the chance to understand this algorithm. Here's a little (annotated) gist I made after understanding it: https://gist.github.com/quantumelixir/3c410dd4a0afe0f2514e0f...
The algorithms for computing it are beautiful and have enabled much of the technology we see around us today.
The algorithm itself is interesting enough, but when applied to bipartite graphs, you can solve some tough problems very efficiently. For instance, one of my favorites is how Santa could possibly match a million kids with a million different gifts in order to maximize happiness. It turns out you structure the problem as a bipartite graph with nodes on one side for gifts and children on the other, and Ford-Fulkerson can guarantee the best matching in polynomial time (no small feat, given how many possible combinations there are!)
[1] https://en.wikipedia.org/wiki/Combinatorial_optimization [2] http://gizmodo.com/5934150/the-algorithm-that-controls-your-...
"An elegant method for resolving collisions in hash tables... It has the rare distinction of being easy to implement and efficient both in theory and practice."
It does an amazing job of packing values into N hash tables so there's very little dead space but lookups are very fast.
mostly because they clearly demo the power of human brain.
It is what is used in ML based languages to infer type and apparently Haskell uses it a bit too
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.
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.
I also was fascinated as shit when I learnt about minimax and alpha beta search.
Game theory and neural nets have always fascinated me.
RSA.