  In a seminal paper on finding large matchings in sparse random graphs, Karp
and Sipser proposed two algorithms for this task. The second algorithm has been
intensely studied, but due to technical difficulties, the first algorithm has
received less attention. Empirical results in \cite{KS} suggest that the first
algorithm is superior. In this paper we show that this is indeed the case, at
least for random cubic graphs. We show that w.h.p. the first algorithm will
find a matching of size $n/2 - O(\log n)$ on a random cubic graph (indeed on a
random graph with degrees in $\{3,4\}$). We also show that the algorithm can be
adapted to find a perfect matching w.h.p. in $O(n)$ time, as opposed to
$O(n^{3/2})$ time for the worst-case.
