My current favorite is SWIM. https://www.cs.cornell.edu/~asdas/research/dsn02-swim.pdf
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.
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?
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.
[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
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.
Also best (only?) practical use of the (inverse) Ackermann function!
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.
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...
PHP implementation: https://github.com/bandwidth-throttle/token-bucket
http://nginx.org/en/docs/http/ngx_http_limit_req_module.html
The algorithms for computing it are beautiful and have enabled much of the technology we see around us today.
mostly because they clearly demo the power of human brain.
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
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 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.
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.
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.