Dynamic Programming algorithms and real world usage

Question

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?

Answer 1

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.