This proposal focuses on two aspects of probabilistic methods in the design and analysis of algorithms: the construction of randomized algorithms, which toss coins in the course of their execution; and the probabilistic analysis of algorithms, on the assumption that their input data is drawn from a specified probability distribution. In the area of randomized algorithms, this study will concentrate on four topics: competitive analysis of randomized on-line algorithms, randomized algorithms for enumeration problems, randomized scheduling of parallel computations and randomness as a computational resource. In the area of probabilistic analysis, this study will emphasize the analysis of fast and simple algorithms for the approximate solution of combinatorial optimization problems.
