Too long to read

I've always liked thinking about mathematical problems but never proving their solutions.

This is one of the reasons I got interested in the algorithm competitions. Solutions don't have to be perfect, sometimes they don't even have to be correct. It's just enough that they're working on test cases provided by authors. It makes you creative. You can try different approaches based on your intuition, lucky hunches or just theory of probability (like Monte Carlo method) and hoping for merciful test data. It can be considered as fun in some geeky environments.

I especially like a class of the problems related to, so called, dynamic programming. There are two cases with them: you either see some very simple and elegant (possibly tricky too) solution that is obviously correct or you have no idea how to approach it. Usually it's the latter - those problems are the killers for most of the programmers... They were a bit depressing for me too, because at the beginning I couldn't solve even the simplest ones.

It took me about half a year to gain the basic intuitions about how to approach them. It sounds silly to me right now that I've spent couple of weeks solving classical knapsack problem, but that's the way it goes with them. It could have been faster if I had found any interesting materials on this subject. Actually, I haven't encountered anything good, even after couple of years. There are some nice papers on topcoder site, but they are too short...

I intend to change that! I'll try to post a decent dynamic programming tutorial. It probably won't be easy and I can fail badly but I still want to try. That would be a primary target for this blog for now, but I'm going to write about other things as well so it wouldn't be that boring.

And here is the question: why anyone would like to read anything about it, knowing that dynamic programming is considered as one of the least useful techniques in algorithmics?

Well, it is fun! It exercises your brain providing lots of challenging problems. Most of them have really simple statements without any mysterious terminology, so you don't have to be into it for couple of years to even understand what is to be solved. Besides that, it is often used in the job interviews in the computer science related companies. So it could be worth to give it a try just for this one.

I would like also to write about some other techniques and subjects that could be interesting even for normal people, like game theory for example. Let's see if I have enough energy to do that. If you have any suggestions, complaints or comments feel free to mail me or just put a comment below.

I'll try to keep posting more or less regularly.