4

Im learning dynamic programming now, and while I know the theory well, designing DP algorithms for new problems is still difficult.

This is what i would really like now- A book or a website, which poses a problem which can be solved by dynamic programming. Also there is the solution with an explanation available, which i would like to see if i cant solve the problem even after butting my head at it for a few hours. Is there some resource that provides this sort of a thing for several categories of algorithms- like graph algorithms, dynamic programming, etc?

P.S. I considered Topcoder, but the solutions there are not really appropriate for learning to implement efficient solutions.

Improve this question

4 Answers 4

Reset to default
4

Any of the ACM contest problem sets would probably work. Some places to find such:

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Are solutions available for the UVA online judge?
ACM contest problem sets is the way to go. You'll need to learn how to recognize the problems solvable through DP first, but then these sites are a very good resource.
@Pranav - the second link there provides general explanations of how to solve the problem on each problem's page under the 'Explanation' heading (but doesn't give you an entire solution in code). @Dom/pierr - thanks! :) @laura - the second link actually notes what type each problem is, so the ones that are clearly dynamic programming problems are marked as such.
For DP specifically, algorithmist.com/index.php/Category:Dynamic_Programming tips you off to a few problems in DP. =)
Both links are now broken! Any alternatives?
|
1

Many problems in Project Euler can be solved elegantly by using dynamic programming.

Improve this answer

Comments

1

I disagree somewhat that the solutions on TopCoder are not examples of good practice. The solutions submitted by the top users are often very simple and not necessarily extremely efficient, just efficient enough. What really matters is that the code is very short, which makes it a lot easier to understand, especially if you don't already know the solution.

I don't recommend writing ordinary programs in the same style, but it can definitely teach you something about over-engineering. I've seen solutions in Java with custom iterators, comparators, etc. and they were much harder to understand, even if the algorithm itself was trivial.

I once read an essay by Paul Graham, where he states that programs with fewer tokens are easier to understand. TopCoder has convinced me that this is true, at least in some domains.

Improve this answer

Comments

0

http://www.topcoder.com
Here you will find all types of questions of varying difficulty level.

Improve this answer

4 Comments

As i said- the solutions there are not really appropriate for learning to implement efficient solutions.
@Pranav Yes some of the questions are not beginner level, but you need to start from somewhere.
That not what i meant. The solutions there are quite inefficient and are just put together to solve the problem in the minimum possible time. Not easy to understand and definitely not a good guide for good programming practices.
@Pranav Sorry, but you're QUITE wrong by The solutions there are quite inefficient. TopCoder "algorithm compititions" are specialized in designing algorithms. I don't think you can find another similar place to learn & develop algorithms. About "programming practices" this is not important at all in field of alogrithms. The important is how efficient your code is.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.