Lecture, four hours; outside study, eight hours. Basic concepts and design techniques for randomized algorithms, such as probability theory, Markov chains, random walks, and probabilistic method. Applications to randomized algorithms in data structures, graph theory, computational geometry, number theory, and parallel and distributed systems. Letter grading.