Tuesday, September 21, 2010

Dynamic Programming


Dynamic Programming is method of solving complex problems by breaking them down into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problems.
    It is a powerful design technique that can be used to solve problems of computational nature. And it is typically applied to optimization problems.

Keys of Dynamic Programming:
1. Optimal substructure
    An optimal solution to a problem (instance) contains optimal solutions to subproblems.
2. Overlapping subproblems
    A recursive solution contains a “small” number of distinct subproblems repeated many times.
3. Bottom Up Fashion
    Computing the solution in a bottom-up fashion to solve the problem.

Areas:
  • Bio-informatics
  • Control theory
  • Information theory
  • Operations research
  • Computer science: theory, graphics, AI, systems
Some famous dynamic programming algorithms:
  • Unix diff for comparing two files
  • Viterbi for hidden Markov models
  • Smith-Waterman for sequence alignment
  • Bellman-Ford for shortest path routing in networks
  • Cocke-Kasami-Younger for parsing context free grammars