An Introduction to Randomized Algorithms

TitleAn Introduction to Randomized Algorithms
Publication TypeTechnical Report
Year of Publication1990
AuthorsKarp, R. M.
Other Numbers588

Research conducted over the past fifteen years has amply demonstrated the advantages of algorithms that make random choices in the course of their execution. This paper presents a wide variety of examples intended to illustrate the range of applications of randomized algorithms, and the general principles and approaches that are of greatest use in their construction. The examples are drawn from many areas, including number theory, algebra, graph theory, pattern matching, selection, sorting, searching, computational geometry, combinatorial enumeration, and parallel and distributed computation.

Bibliographic Notes

ICSI Technical Report TR-90-024

Abbreviated Authors

R. M. Karp

ICSI Research Group


ICSI Publication Type

Technical Report