Randomized algorithms
by Rajeev Motwani · first published 1995
57% recommend43% neutral
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2011–2025Probability and Computing
Michael Mitzenmacher, Eli Upfal
Recommended by 4 · mentioned by 84 recommend · 8 mention4 recommend · 84 recommend
2014–2025Grokking Algorithms
Aditya Y. Bhargava
Recommended by 42 · mentioned by 5942 recommend · 59 mention42 recommend · 5942 recommend
2007–2026The algorithm design manual
Steven S. Skiena
Recommended by 195 · mentioned by 265195 recommend · 265 mention195 recommend · 265195 recommend
2007–2026Programming Pearls
Jon Bentley
Recommended by 158 · mentioned by 245158 recommend · 245 mention158 recommend · 245158 recommend
2007–2026The art of computer programming
Donald Knuth
Recommended by 336 · mentioned by 1,125336 recommend · 1,125 mention336 recommend · 1,125336 recommend
2007–2026Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Recommended by 274 · mentioned by 712274 recommend · 712 mention274 recommend · 712274 recommend
Randomized Algorithms by Raghavan and Motwani. I've been researching/teaching these topics for many years and still find some new insight every time I open this book.
on “If you could only have one programming book on bookshelf what would it be?” ↗…Algorithms you will need to cover quite a bit of additional material. Numerical methods -- Numerical Recipes 3rd Edition: The Art of Scientific Computing by Tuekolsky and Vetterling. I love this book. [5] Randomized algorithms -- Randomized Algorithms by Motwani and Raghavan. [6], Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher, [7] Hard problems (like NP) -- Approximation…
on “Ask HN: Any recommendations on resources for learning one algorithm a day?” ↗…addition to being much more mathematically self-contained, there is more focus on models and techniques that I imagine software engineers might actually use, e.g. hashing, load balancing. In addition, Randomized Algorithms by Motwani and Raghavan is a fantastic book, and should be doable after completing Mitzenmacher and Upfal. It goes into further depth on techinques for designing randomized algorithms. A bit orthogonal…
on “Data structures and algorithms I actually used while working at tech companies” ↗For those who were confused (as I was), Prabhakar Raghavan wasn't the one who recently died, it was his co-author in Randomized Algorithms, Rajeev Motwani. BTW, I highly recommend their book. In it is all the evidence of the genesis of Google.
on “Yahoo Wants to Blind the Competition With Science” ↗…He also co-authored another seminal search paper What Can You Do With A Web In Your Pocket with those same authors.[3] He was also an author of two widely-used theoretical computer science textbooks, Randomized Algorithms (Cambridge University Press 1995, ISBN 978-0-521-47465-8, with Prabhakar Raghavan) and Introduction to Automata Theory, Languages, and Computation (2nd ed., Addison-Wesley, 2000, with John Hopcroft and…
on “The IIT Entrance Exam” ↗…random pivots, damnit! :) The article you point to doesn't seem to address the complexity of quicksort with random pivots. However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned.
on “Beating Binary Search” ↗…experimental algorithmics, and avoids discussions of things which aren't practical (such as using truly random pivots). > However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned. Right, but since there are no truly random quicksorts, its hardly a concern.
on “Beating Binary Search” ↗