This significantly expanded new edition requires only a basic understanding of discrete mathematics and provides a comprehensive introduction to the role of randomization and probabilistic techniques in modern computer science. Newly added chapters and sections cover topics such as normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz lemma. Materials relevant to machine learning and big data analysis enable students to learn modern techniques and applications. Among the many new exercises and examples are programming-related tasks that offer students excellent training in solving relevant problems. This book is an essential teaching resource for a one- or two-semester course for advanced students in computer science and applied mathematics.