Randomized algorithms

There are some books about algorithms that are not well-known in Russia (in my opinion), but still are really good.

One of them is “Randomized algorithms” by Rajeev Motwani and Prabhakar Raghavan. It is rather easy to read, but describes a lot of important ideas and is fairly well-written (as is another more famous book by Motwani et al. Introduction to Automata Theory, Languages, and Computation). It’s a great loss that Rajeev passed away several months ago and we won’t be able to see more exciting books written by him.

Advertisements

2 Comments to “Randomized algorithms”

  1. Да, книжка хорошая и малоизвестная в России. Я ее как раз сейчас смотрю. Радует параграф про приближение перманента.

    • I was really impressed by Yao’s minimax principle, because it uses well-known game theoretic technique for giving lower bounds for randomized algorithms, considering a “game” between algorithms and inputs =)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: