Fiction about algorithms

Some time ago I had a question in my livejournal blog (in Russian) about books on project management. There I was given a nice advice to read The Goal by Eli Goldratt.

This turned out to be really interesting, one of the reasons of this being that in a steady way of a fiction book it discusses problems, that are quite familiar to those who know something about combinatorial optimization. Here you will meet some old friends like “Maximum flow” and “Two-route Johnson’s problem” (which seems to be much better known in Russia than anywhere else). However, they will look a bit different seen from the point of view of people who want to do all the optimization in real life. Probably some books on operational research and linear programming that can be found at any department of economics will give the same impression. Well, but reading a fiction book has its own fun anyway.

Do you know other fiction books that deal with algorithms or people who worked on them? Recently I tried to find some interesting autobiographies, memoirs or something about great computer scientists, but failed (well, in fact I found Bellman’s biography mentioned in Richard Lipton’s blog, but it seems to be impossible to get). Do they exist? Unfortunately, I don’t even expect these books to be as exciting as are books about Feynman for physicists.

Monotonicity testing

This is a post about an open problem that was given to me by Sofya Raskhodnikova last summer. The problem turned out to be rather difficult and I still don’t know the solution. Even on mathoverflow I got no answer about what methods to try. However, it can be described rather easily (you can see the description following the link to mathoverflow).

Here I will try to explain (very informally) what it has to do with algorithms and particularly testing monotonicity in sublinear time. I suppose that you have read the description of the problem.

Now suppose that we are trying to test a function for monotonicity using the following test: picking an edge of the hypercube at random and querying the values on its ends, if the edge is not monotone then we say “NO”, otherwise we continue the process. After some iterations we stop and say “YES”.

The problem is to prove that if the function is -far from being monotone then after small number of iterations we will find a non-monotone edge with high probability. Here -far means as usually with property testing problems that the minimal fraction of vertices at which the value of the function needs to be changed to make it monotone is . So we want to show that if there are many vertices, where the values need to be changed to make the function monotone, then there must be many non-monotone edges. Turning to contrapositive: if there are just a few edges then we can change values in a small number of vertices to make the function monotone. This is exactly what the described open problem is about.

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.

Classic puzzle revisited

Here is a classic algorithmic puzzle probably taken from some interview. You are given integer numbers such that all of them but two can be grouped into pairs in which elements are equal. The goal is to find two numbers that have no pair in time .

The solution is described below, so you should stop here if you want to solve it yourself.

The well-known solution for this puzzle consists of taking XOR of all the numbers , finding any position in its binary representation such that and then giving as an answer two numbers: and .

Considering this problem as a good exercise for understanding XOR operation, we decided to give it to children on our elective course in olympiad programming (in Russian). The only team that managed to solve it invented a somewhat different solution. Having calculated , they calculate two numbers as an answer: and .

It took me a few moments to understand why does this work. I was really excited when I did — it is an incredible pleasure working with talented children!

This puzzle is a difficult version of a simpler one, in which there is only one number without a pair. Unfortunately, I don’t see how the ideas described above can be modified to handle three or more numbers that have no pair. I think this is impossible to do in time, isn’t it?