6
$\begingroup$

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$.

This problem has a stunning solution running in $O(n)$ time and using 2 words of space only, attributed to Bob Floyd (at least by Knuth). The crux is to see this as a cycle finding problem (even though there is zero mention of a cycle let alone a graph), and employ the so called Tortoise and Hare algorithm (again, by Floyd).

This Tortoise and Hare algorithm was later used by Pollard in his factoring algorithm and somewhat recently extended here to solve the element distinctness problem using small space.

What are some other uses of this algorithm or extensions of it in TCS?

New contributor
boinkboink is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 1
    $\begingroup$ Pollard used for dlog. Do you have references for factoring? $\endgroup$ – Turbo Jul 11 at 23:11
  • 1
    $\begingroup$ @Turbo en.wikipedia.org/wiki/Pollard%27s_rho_algorithm $\endgroup$ – boinkboink Jul 12 at 0:01
  • $\begingroup$ Maybe not in TCS, but it can be used to find collisions in Hash Functions with $O(2^{n/2})$ time and just a bit of memory. $\endgroup$ – Hyperflame 15 hours ago

Your Answer

boinkboink is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.