5 Dec 2008 nuncanada   » (Journeyer)

Dynamic Programming is a nice general procedure to attack some specific exponential algorithms and reduce them to polynomial time. But beware, they aren't usually created taking in mind the symmetries of the problem in question, so they may leave a lot to desire to come close to a algorithm designed with the given problem in mind.

So for instance, matrix chain multiplication which is a textbook example for dynamic programming will give out a O(n^3) algorithm. There are much better algorithms for this problem out there, specifically a O(n*log n) one.

Just after i first was taught about the chain matrix multiplication problem and it's dynamic programming solution i couldn't believe that was the best algorithm that could be done for it. Some days later after trying first to find an algorithm and then looking a lot around the internet i finally found this paper. Thanks Hu and Shing for the great work and taking out my obsession with this problem.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!