An Introduction to Randomized Algorithms
Title | An Introduction to Randomized Algorithms |
Publication Type | Technical Report |
Year of Publication | 1990 |
Authors | Karp, R. M. |
Other Numbers | 588 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-024.pdf |
Bibliographic Notes | ICSI Technical Report TR-90-024 |
Abbreviated Authors | R. M. Karp |
ICSI Research Group | Algorithms |
ICSI Publication Type | Technical Report |