An introduction to randomized algorithms (Q1182319)

The concept of randomization is known to be an extremely important tool for the design of algorithms. Its use often yields better time or space complexity compared with the best deterministic algorithms we know of for the same problem; moreover resulting randomized algorithms are often very simple to understand and implement. The article starts with the brief survey of some basic principles which can be traced in the construction of randomized algorithms. These principles are then illustrated on a survey of randomized algorithms for problems in number theory, algebra, pattern matching, sorting and searching, computational geometry, graph theory, combinatorial enumeration, and distributed computing. For the sake of brevity proofs of the theorems and lemmas are mostly omitted and the algorithms are presented in a semi-formal style, yet the article is an example of a nice and understandable exposition of the advantages of algorithms that make random choices in the course of their execution.