6

I have studied in the past the classical DP problems and algorithms (coins, longest increasing subsequence, longest common subsequence, etc).

I know that these algorithms have practical applications (ie. genetic algorithms, just to name one). What I question though is if these algorithms have practical applications in modern computer science, where the size of input is very large and problems are not solvable on just one machine.

My point is that these algorithms are quite hard to parallelize (ie. Parallel Dynamic Programming), and memory occupation is quadratic in most of the formulations, making it hard to process inputs that are reasonably big.

Anyone has real world use cases on this?

Community
  • 1
  • 1
Savino Sguera
  • 3,522
  • 21
  • 20
  • 2
    Memory occupation is quadratic but the time saved is worth every single byte. Write 2 implementations of a program computing Fibonnaci sequence based on reccurence relation, one with a cache and another without. Profile, and see the results. – UmNyobe Feb 06 '12 at 10:28
  • 1
    @UmNyobe: fibonachi is not a good example, it can be solved in `O(1)` :) [though I agree with your point, of course]. – amit Feb 06 '12 at 10:28
  • that's why I said based on recurrence relation. I took Fibonnaci as an example because it can be done in 30 mins. – UmNyobe Feb 06 '12 at 10:31
  • Fibonacci uses memoization, not DP, though. I agree that's related. – Savino Sguera Feb 06 '12 at 10:32
  • 1
    LCS can be solved using linear space. The time can be brought down to linear as well by putting a max bound on the LCS, I think. – Fred Foo Feb 06 '12 at 10:33

2 Answers2

5

Practical application: diff. This is an essential Linux utility which finds the differences between two files by solving the longest common subsequence problem using the DP algorithm.

DP algorithms are used because in many cases they are the only practical solution. And besides, there is nothing wrong with them.

Memory usage: Often, a sliding window can be used to reduce the memory usage dramatically. Fibonacci, when solved using a naive bottom-up DP, requires O(n) memory. A sliding window improves this to O(1) memory (I know of the magical constant time solution, but that's beside the point).

Parallelization: Top-down DPs are often easy to parallelize. Bottom-ups may or may not be. @amit's example (parallelizing longest common subsequence) is a good one, where any given diagonal's tiles can be solved independently as long as the previous diagonals are known.

tom
  • 21,844
  • 6
  • 43
  • 36
1

The longest common subsequence problem and Longest common substring problem are sometimes important for analyzing strings [analyzing genes sequence, for example]. And they can be solved efficiently using dynamic programming.

Note you can parallelize this algorithm: you do it in iterations on the diagonals [from left,down to right,up] - so total of 2n-1 iterations. And in every diagonal: each cell does not depend on other cells in this diagonal - so parallelizing can be done here, each thread will have a block of cells in this diagonal.

Note that data synchronization using this method is also minimal: each thread needs only to transfer data to his "neighboring threads" so it can be done even if the memory is not shared.

Also, both problems, as @larsmans mentioned - can use linear space - at each point you only need to "remember" the current + 2 last diagonals, and not the entire matrix.

Another common problem that is solved using dynamic programming is polynomial interpolation. The interpolation can be effieciently done using Newton Interpolation, which first needs to calculate the divided differences - which is built using dynamic programming.

amit
  • 175,853
  • 27
  • 231
  • 333
  • I know that they are useful for genetic algorithms (I improved the question). I am questioning whether these are practical for non-trivial input size. – Savino Sguera Feb 06 '12 at 10:24
  • @SavinoSguera: (1) I editted and added an extra application for practical dp. (2) I introduced in my answer how you can parallelize this algorithm - so these algorithms are scalable, using these parallelization methods. You can even use [map reduce](http://en.wikipedia.org/wiki/MapReduce) iteratively and build the matrix on the fly, since the data in each iteration [as I presented it] does not depend on each other. – amit Feb 06 '12 at 10:27
  • @SavinoSguera Also, note that [genetic algorithms](http://en.wikipedia.org/wiki/Genetic_algorithm) and algorithms for genetic analyzis are not the same thing – amit Feb 06 '12 at 10:30