Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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, polynomial reductions and approximation algorithms for four nice tutoring sessions.

share|improve this 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.