[boost] GSoC 2013 : Implementing Dynamic Programming Algorithms

Subject: [boost] GSoC 2013 : Implementing Dynamic Programming Algorithms
From: Aman Gupta (amangupta052_at_[hidden])
Date: 2013-04-08 19:22:30

Hi,

I am Aman Gupta from BITS-Pilani India, I am a 4th year Undergraduate
Student majoring in Computer Science.

I've noticed that boost does not contain dynamic programming algorithms
like Integer-Knapsack, Longest Common Sub-sequence.

I was thinking that implementing this would be a good project. I realize
most of these problems are non-polynomial in complexity but I was thinking
implementing them to a
certain size will not be problem.
Also, since some of the dynamic programming algorithms have alternate
greedy algorithms which compromise on correctness but are faster,
implementing those can be useful.
The knapsack problem(which comes in a lot of situations) for which there
exists an algorithm which gives an arbitrarily close approximation to the
optimal value can be implemented.
( e.g. f(weights,values,error)  could be the function, the user has a
trade-off between error and computation time).
I think it could be useful in situations where the user just decides the
error he wants or perhaps how fast he wants his computation.

Please let me know if this seems like a valid project idea to you!

Thanks,
Aman Gupta