I haven’t been posting for the past few days because I’ve been in Wrocław (Breslau) for the weekend and then I was kinda busy playing with new coding quests, this time from topcoder.com, my second big love after Project Euler (jeez, why nobody told me about these two before? 😉 ). I’ve noticed that usually three out of four tasks require use of dynamic programming, which is a really nice and powerful technique. Unfortunately sometimes I’m stuck with a quest, for which I’ve already spotted quite a nice DP solution but while it lacks all the possible optimizations (usually quite sophisticated, which require a lot more thinking than the first approach that comes to mind) it’s sometimes significantly slower than the best possible solution. Nevertheless, 9 out of 10 times 😉 it is very educating to run a not-quite-perfect algorithm because it lets one spot the possibilities for optimization and understand the problem better as a whole. Though still… it would be nice if it ran a little bit faster 😉 Parallelization seems to be the keyword here. If you google for it in the context of DP you’re bound to find quite a few publications. Most of them focus on parallelizing DP algorithms in specific domains (e.g. biology, process control, physics, etc.), but there is also a few of them that strive to generalize the problem. I strongly believe that generalization in this matter is both possible and quite self-evident. I’m going to discuss it taking one of the recent DIV1 500-point TCO problems as an example. Not sure yet if I can quote it though, going to email TCO about it.
I’ve also been using Boost Graph Library (BGL) in the mentioned application so you will see some practical usage examples of it too. It seems crazy at first but in fact it’s a very powerful and flexible framework. Pretty fast too. Stay tuned.