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.
Re: Algorithm dynamic programming recipes (response to post by syg96) | Reply
I'm not sure yet how exactly "Introducing DP" will look like. The only current draft is this, but it will need some more work. It probably should contain the "General DP things" of your plan, since they are really not about optimization.

As for two next parts of your plan, they look excellent! But it seems to me that "Commonly used state domains" should be a separate recipe, especially if it's not just mentioning each point but expanding it with explanations when it is applicable and problem examples - it's going to be really useful. Maybe you'd like to split your plan in two recipes and do both?
Re: Algorithm dynamic programming recipes (response to post by Nickolas) | Reply
Yes, it is a good idea! This plan is too long right now...
But the recipe about state domains will still contain few optimizations (Knuth trick, iteration over subsets, broken profile) specific for the state domains described.

Ok, so I assume that forward/backward dynamics and ways to restore path will be described in Introducing DP recipe.
Re: Algorithm dynamic programming recipes (response to post by syg96) | Reply
Sounds really great. I can't wait to read it.
Re: Algorithm dynamic programming recipes (response to post by syg96) | Reply
Have you finished it?