Probabilistic methods and randomized algorithms

UnrestrictedAn algorithm can be defined as a set of computational steps that transform the input to the output. Probabilistic analysis of algorithms is the method of studying how algorithms perform when the input is taken from well defined probabilistic space. In design of algorithms to solve many important problems, randomized algorithms are either the fastest, or the simplest algorithms, and often both.; In this study, different probabilistic methods will be investigated. Useful and well known bounds such as Chernoff bounds and Ramsey theory, first and second moment methods and Lovasz local lemma (LLL) are considered to analyze the algorithmic and combinatorial problems of interest. Pure and accelerated random search algorithms and some of their convergence properties will be considered in the last section.; We'll see that the gains in random algorithms come at a price that the answers may have some positive probability of being incorrect. Although it may seem unusual to design an algorithm that may be incorrect, if the probability of error is sufficiently small then the improvement in speed or memory requirements may well be worthwhile