ISBN 9780521613903,Randomized Algorithms

Randomized Algorithms



Cambridge University Press

Publication Year 2010

ISBN 9780521613903

ISBN-10 0521613906

Paper Back

Number of Pages 492 Pages
Language (English)


After the first randomized algorithm was envisaged by Michael O. Rabin, a number of investigations and studies were undertaken into the nature of the algorithm. A randomized algorithm provides the easiest albeit the fastest algorithm that may be present in an application and therefore grew in prominence. It technically uses randomness as part of its logic and this book, Randomized Algorithms provides all the structured that are engaged in design and analysis of these algorithms.

The textbook plays out as a tutorial whereby the construction and application of randomized algorithms take center stage. The book contains two sections whereby the first section deals with the Tools and Techniques intimate to the randomized algorithm and the second deals with the applications related to the same.

The first section contains seven chapters and it begins by elucidating upon the Min-Cut Algorithm and Computation Models. Through this section it then branches out to Probabilistic Methods, game theoretic techniques and algebraic techniques amongst a number of other concepts. Each chapter ends with highlights and problems to engage students more intensively.

The second section then takes up the cause of the applications that are spurned through the use of Randomized Algorithms. Beginning with Data Structures, it moves on to Linear Programming, Graph Algorithms, the Method of Approximate Counting, Parallel and Distributed Algorithms, Online Algorithms and ends with the Number Theory and Algebra.

Aimed at the advanced undergraduate and graduate students of Computer Science, Randomized Algorithms is an accessible textbook that is widely. It is also nimble enough to cater to researchers and programmers interested in the field of algorithms that seek to use this book as a reference point for their investigations. Written in 1995, it has been veritably lauded as a standard on the subject of randomized algorithms.

About The Authors

Rajeev Motwani was a distinguished member of the faculty at Stanford University where he taught computer science.

After co-authoring a seminal paper on PageRank Algorithm, he went on to write Randomized Algorithms and Introduction to Automata Theory, Languages And Computation.

He was born in Jammu and grew up in New Delhi. After completing B.Tech from IIT, Kanpur he went onto U.C. Berkeley and received a Ph.D degree. He went on to fame and fortune after moving overseas and joining Stanford University as a professor. His research around theoretical computer science won him the Godel Prize in 2001. He died in 2009, leaving behind his wife, Asha Jadeja and his two daughters.

Prabhakar Raghavan works at Google as their Vice President of Engineering.

Apart from Randomized Algorithms, Raghavan has also authored Introduction To Information Retrieval.

He is also a member of the National Academy of Engineering and a Consulting Professor at Stanford University. He was conferred with the Laurea Honoris Causa from the University of Bologna, in 2009. He earned a Bachelor in Technology from IIT, Madras after which he went on to complete his Ph.D. in Electrical Engineering and Computer Science from U.C. Berkeley.