Is there a good book specialized in exercises on finding recurrence cause i want to train on (dynamic programming) cause i find myself a lot knowing that a problem can be solved dynamically but i can't find the recurrence function .
views:
230answers:
4
A:
The only book I've read that deals with dynamic programming is "Algorithm Design" by Kleinberg and Tardos.
However, it only spends one chapter on dynamic programming so it probably isn't worth buying the whole book just for that. However, if you're interested in algorithm design in general, this book is very good, and the chapter on dynamic programming was well explained.
Michael Patterson
2010-04-03 22:46:37
Well thank you, i was searching for a good algorithm book and i didn't know what to get either "Algorithm design manual" by Steve Skiena or "Introduction to algorithms" By Cormen or this one ... so what do you recommend ?
magiix
2010-04-04 07:07:48
The book I mentioned is the only algorithm specific book I've really gone through, so I can't really compare it to others. However, I would say it provides a very good overview of many algorithms, but it never goes into a great deal of detail. The code examples are all pseudo-code and pretty high level. I think the best part is that the common patterns it describes can be applied to solve many different problems. I wish I could be of more help, but I can't really compare it to any other algorithm books.
Michael Patterson
2010-04-04 07:38:04
A:
Maybe I didn't understand your request, but reccurence function is a generic approach, opposite to iterational algorithm which goes through the list.
So if you'd like to go deeper into that topic read some basic Lisp, scheme books. Many algorithms base on recurenction there.
Simple approach of recurence would incude:
- entry point
- check is the iteration the last one
- if no, invoke the same function again
if yes, return value
foo(list, cnt) { if (cnt<=0) return 1 else return foo(&list[1], cnt-1) }
foo( {1, 2, 3, 4} , 3)
bua
2010-04-03 22:49:11
the question is about dynamic programming, not just recursion. Dynamic programming is about finding optimal solutions to problems by using memoization and recursion techniques.
Nick D
2010-04-03 23:16:58
A:
Brian Dean's Dynamic Programming Practice Problems isn't a book, but it seems to fit the bill.
Charles Stewart
2010-04-20 09:09:36
A:
For the math behind dynamic programming, Eric Denardo's book is great. It's approachable and rigorous at the same time.
For learning algorithmic techniques in general, the single best investment you can make is the good old CLRS.
For actually learning how to apply dynamic programming, you'll want to hit the algorithmic challenge sites: TopCoder, SPOJ, USACO, the Uva Online Judge, etc.
rtperson
2010-05-04 21:08:43