As the networks are prone to say during the summer, "If you haven't seen it, it's new to you".
Cambridge University Press has cornered the market on randomized algorithms. After publishing the truly excellent Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan (ed: wasn't Rajeev your advisor ? me: that has nothing, nothing at all to do with it), they have now published Probability and Computing by Michael Mitzenmacher and Eli Upfal. I caught a brief look at the book the other day, and it seems to have a slightly higher focus on probabilistic tools and techniques and possibly a slightly lesser focus on randomized algorithms, but I could be wrong here.
All in all, looks like a great book to have; it's definitely on my list of books-to-get.
no, you are definitely right, more on probabilistic analysis and less on the pure randomized algorithms. In particular, I think balls and bins, ballanced allocations, a little bit of coding/information theory, and pairwise independent hash functions are mentioned quite a bit (which I don't think have too much emphasis in Motwani and Raghavan).
ReplyDeletePosted by Anonymous
As a lurker on the Geomblog, I was very excited to see my new book mentioned! Thanks Suresh!
ReplyDeleteWhile obviously there is some overlap with the (excellent!) Motwani and Raghavan book, Eli Upfal and I did consciously set out to make a different book. First, as you noticed, we tried to cover some different topics. I'm particularly pleased to have included a chapter on entropy, a topic that doesn't generally get covered as part of a CS education (at least for undergraduates), although it should.
The second big difference is that this book was really designed to be a textbook, specifically aimed at a lower level than Motwani and Raghavan. We primiarly designed it for a class for juniors/seniors/first-year grad students, who may not all be theory folks. This isn't to say there won't be interesting stuff for more advanced types (I hope!), but we're hoping the book is more generally accessible.
So I hope the clear message is that I think every bookshelf should have both books! The books have a lot of disjoint material, and hopefully our book is appropriate preparation for the more advanced Motwani and Raghavan is a more advanced book.
If you want to throw an extra kickback my way, please buy the book from the Amazon link on my home page .
Posted by Michael Mitzenmacher
This comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteAnother exciting new book is Kleinberg and Tardos' book "Algorithm Design":
ReplyDeletehttp://www.aw-bc.com/info/kleinberg/
Posted by Anonymous