Math Girls 4: Randomized Algorithms, Paperback/Hiroshi Yuki

This fourth entry in the highly acclaimed Math Girls series focuses on the mathematics of computer science and analysis of algorithms. Algorithms generally strive to take the shortest route to their goal, so how is it that adding a random element to how they work can improve their performance? Further, how can we apply mathematics to quantitatively compare the performance of different algorithms? Is it possible to predict the limits of how well an algorithm can perform, without coding and running it on an actual computer? New "math girl" and talented programmer Lisa will join Miruka and friends to explore these and other questions, applying what they learn to well-known algorithms such as bubble sort and quicksort. Other topics explored in this book include the Monty Hall problem, permutations and combinations, Pascal's triangle, the definition of probability, sample spaces, probability distributions, random variables, expected values, big-O notation, matrices, linear transformations, matrix diagonalization, random walks, the 3-SAT problem, and the P-versus-NP problem. Math Girls 4: Randomized Algorithms has something for anyone interested in mathematics and computer science, from advanced high school students to college students and educators.