Some other discrete probabilistic algorithms

We analyzed a probabilistic min-cut algorithm. A cut in a connected undirected multigraph G is a set of edges whose removal results in G being broken into two or more components. A min-cut is a cut with minimum cardinality. Our algorithm successively removes a random edge until a cut occurs. By repeated applications of the algorithm the probability that a min-cut is not found can be as small as you like.

A probabilistic algorithm for searching a pointer ordered list having n elements was analyzed. It uses sqrt(n) random explorations to find a starting point "near" the target element. We showed that the expected number of comparisons needed to find the target element is O(sqrt(n)).

A hash structure, Overflow Indexing (Törn), utilizing a prime memory table giving the bucket addresses to all overflows was analyzed. It was shown that this overflow technique is feasible even for large files. The number of probes for search, deletion, and insertion are 1, 2, 2-3 respectively.