Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Algorithm dynamic programming recipes | Reply
I plan to write the "Optimizing DP solution" recipe. I've read the article "Dynamic programming: from novice to advanced". It is a good as a DP tutorial but lacks not only time/memory optimizations, but also commonly used state domains (i.e. subsets, vertices of tree, segments, etc) and clear note of difference between forward and backward dynamics (top-down and bottom-up in wikipedia). Will the "Introducing the DP" be similar in this way?

The plan for the recipe is now the following:

General DP things:
1. Difference between forward/backward dynamics.
2. How to reconstruct path after DP (store best/recalculate).
3. Memoization = lazy DP.
Here must be a reference to "Optimizing recurse solutions" and brief words about when and why memoization is better than ordinary DP.

Commonly used state domains:
4. Multidimensional array, ordered by component-wise <=.
Not sure that I should write a lot here since it is the usual DP.
5. Subsets, ordered by inclusion
Here must be a reference to recipe about iterations over subsets (overall O(3^n) time complexity)
6. Substrings of a string, ordered by length.
Here Knuth's trick will be described.
7. Vertices of tree, ordered by ancestry
Here should be a note about time complexity analysis.
8. With profiles + broken profiles.

General optimizations:
9. Parameter dependence in solution space
Eliminating the parameter which is clearly determined from the other parameters.
10. Storing fixed number of layers only.
Reducing memory of DP if recurrent relations deal with R[i] and R[i+1] only. Also I'm not sure whether I should describe here divide-and-conquer approach for getting the path (don't remember problems that require this trick).
11. Precalculation.
Quite general words about precalculating values before DP. Binomial coefficients, prefix sums, minimums etc.
12. Rotating solution-result problem.
It's when state parameter becomes result and result becomes state parameter. Like minimizing size of objects which have overall cost C in Knapsack instead of maximizing overall cost of objects which have size W.
13. Not using unnecessary states.
Here the simple approaches to accelerate solutions in constant times are described. Like setting tight bounds on loop variables, ignoring states with zero/infinity result since they have no effect.
14. Storing possible states in the map.
Just mention that it is possible.
15. Binary matrix multiplication.
Mostly combinatoric problems can be solved with this thing.
16. Acceleration with binary search or segment trees or the like.
Notes that sometimes complex data structures are necessary. Seldom used in SRMs.

And of course "Discussion" will be full of real SRM problems and detailed explanations how to solve them.
Subject Author Date
Algorithm dynamic programming recipes syg96 Dec 25, 2010 at 4:55 AM EST
Re: Algorithm dynamic programming recipes Nickolas Dec 25, 2010 at 1:51 PM EST
Re: Algorithm dynamic programming recipes syg96 Dec 26, 2010 at 3:11 AM EST
Re: Algorithm dynamic programming recipes hacker007 Jan 12, 2011 at 10:45 AM EST
Re: Algorithm dynamic programming recipes [torayeff] Oct 29, 2012 at 11:02 AM EDT
Re: Algorithm dynamic programming recipes LifeMaker Jan 4, 2013 at 1:47 AM EST