The field of random graphs contains many surprising and interesting results. Here we demonstrate how some of these results can be used to develop stimulating, open-ended exercises for courses in algorithms and data structures or graph theory. Specifically, we provide problems for algorithms that compute minimum spanning trees, connected components, maximum flows, and all-pairs shortest paths.
Appears in SIGCSE Bulletin, October 1996. Copyright by them, all rights reserved by them, follow their copyright procedure, etc.