| Love all those books. Hadn't heard of the last one though. Looks like it's available online [1]. And actually, it has a few cool links on its homepage to similar books. In particular, there is a link to this gem [2], which, for example, has a chapter [3] on what appears to be a very interesting generalization [4] of the "master theorem" of CLRS. Another good resource that pages links to seems to be [5], which was recently mentioned on HN. Of course, for an even deeper treatment of asymptotic analysis check out Flajolet and Sedgewick [6]! [1] http://opendatastructures.org/ [2] http://jeffe.cs.illinois.edu/teaching/algorithms/ [3] http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-re... [4] https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method [5] (PDF warning) http://opendatastructures.org/mcs.pdf [6] http://ac.cs.princeton.edu/home/ |
In a nutshell, dynamic programming is recursion without repetition. Dynamic programming algorithms store the solutions of intermediate subproblems, often but not always in some kind of array or table. Many algorithms students make the mistake of focusing on the table (because tables are easy and familiar) instead of the much more important (and difficult) task of finding a correct recurrence. As long as we memoize the correct recurrence, an explicit table isn’t really necessary, but if the recursion is incorrect, nothing works.
Dynamic programming is not about filling in tables. It’s about smart recursion!
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-dy...