  We present an algorithm CRE, which either finds a Hamilton cycle in a graph
$G$ or determines that there is no such cycle in the graph. The algorithm's
expected running time over input distribution $G\sim G(n,p)$ is $(1+o(1))n/p$,
the optimal possible expected time, for $p=p(n) \geq 70n^{-\frac{1}{2}}$. This
improves upon previous results on this problem due to Gurevich and Shelah, and
to Thomason.
