Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was offered by a professor to give some tutoring in his course of Algorithm Design, based on Kleinberg and Tardos' book. He suggested me to prepare two exercise on dynamic programming, one exercise for polynomial reduction, and another one for approximation algorithms.The exercise should be not too advanced, but not just routine (they should fill two hour of tutoring).

Then my question is: what are fascinating problems one can propose in dynamic programming?

share|cite|improve this question

closed as too broad by D.W., David Richerby, Kyle Jones, Luke Mathieson, André Souza Lemos Jun 23 '15 at 12:39

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

The exercises in the K-T textbook are generally pretty good. Pick some from that book that the professor is not already using for homework. – Joe Nov 18 '12 at 3:42
You can find too many good DP problems on Top Coder site. If you see the algorithm matches, there are 250 and 500 point problems which are not so hard and not so easy. (depends to your definition of hardness, you can check both types). – user742 Nov 18 '12 at 12:14
CLRS also have many exercises (but no solutions, which is a plus for you). – Raphael Nov 19 '12 at 18:16
This is a tad too broad for a single question; I'm removing two topics. – Raphael Jun 22 '15 at 8:52
It still seems too broad to me. We want focused, technical questions that admit a single objectively correct answer. This seems to call for a "big list of X": a big list of dynamic programming exercises. Such a list could be enormous. I don't see how you'd pick a single objectively correct answer. As such, it seems too broad for this site's format: fascinating question, but not a good fit for Stack Exchange sites, I'm afraid. – D.W. Jun 22 '15 at 22:40