Another Monday is upon us, and another batch of links is due. This week I’m going to focus on Dynamic Programming (or DP for short). The reason is that upcoming Project Euler problems are DP- and memoization heavy. Another reason is that DP problems are quite popular, so it’s definitely a good skill to have.

First up is a TopCoder Algorithm Tutorial, namely Dynamic Programming: From novice to advanced. This is a good “first look” at DP. It’s a bit heavy in the end, but that part can be skipped.

After you’ve read that, you should take a look at Bruce Merry‘s introduction to Dynamic programming. It’s got a really great step-by-step approach to solving a DP problem, which in my experience works quite well.

Now you should have a good idea of how DP works. Next I suggest you go over these Dynamic Programming Practice Problems presented by Brian C. Dean. These are good video tutorials covering a few common DP problems.

Now you should be able to solve some real DP problems. A great list of DP problems is the Dynamic Programming Problem Set on the Timus Online Judge. Start with the easiest problem (the problems are sorted by difficulty, and the easiest is the topmost problem). Read the problem description and then use Bruce Merry’s step-by-step approach (from above) to solve it. Don’t worry if you can’t, DP is a tough nut to crack and the only way to become good at it is to practice and practice.

One more DP link I think I should mention is our own collection of DP problems: MathBlog posts tagged with “Dynamic Programming”. Kristian has solved many Project Euler problems with DP, and he always manages to explain his method well.

I really think I need to have one extra link for those of you who don’t find the above links interesting. Haskell is a functional programming language every mathematical programmer should know. It’s also insanely beautiful. The final link is a book about Haskell: Learn You a Haskell for Great Good!. I’m currently on the 12th chapter (of 14) and it’s been great to read. The author allows you to read it online, free of charge, but the book can also be purchased to support the author.

And that’s it for this Monday. The blog image is by JanneM, who provided it under the Creative Commons licence. Enjoy the links!

Thanks for these useful sources.

You’re welcome! 🙂

And why are you not posting Uva solutions?

Hehe, glad someone noticed! School starts in a week, and I’ve been busy preparing. I’m hoping things will calm down soon after school starts, and then maybe I can start posting regularly again. I have one easy problem post that is nearly finished. But please, if there is a problem you’re stuck on, or think is interesting in any way, feel free to let me know and I’ll write a post about it. I’m more likely to write a post if it’s specifically requested, rather than if I’m doing it on a schedule. 🙂

ok, when I meet some problem which is interesting or difficult I will tell you. And 1 question. How old are you? 🙂