How (and why) to introduce Monte Carlo randomized algorithms into a basic algorithms course
Yana Kortsarts, Jeffrey Rufinus · Journal of computing sciences in colleges · 2005
We suggest a way of adding the fundamental subject of Monte Carlo randomized algorithms into a basic algorithms course. While this topic was discussed previously (see, e.g., [12]) it mainly concerns Las Vegas (no error) algorithms. Our goal is to present a simple but interesting example of a Monte Carlo (one-side error) algorithm. We discuss the algorithm to find long simple paths in a directed graph due to [2]. The long path algorithm illustrates the subject well, is very easy to follow, and requires minimal understanding in probability. Unlike examples like skip-lists and Randomized Quicksort, our example deals with graphs and that makes it very suitable for teaching in a basic algorithms course. Finally, we note that our example of the Monte Carlo algorithm is drawn from the recent research.