Dynamic Programming - Algorithms That Use Dynamic Programming

Algorithms That Use Dynamic Programming

  • Recurrent solutions to lattice models for protein-DNA binding
  • Backward induction as a solution method for finite-horizon discrete-time dynamic optimization problems
  • Method of undetermined coefficients can be used to solve the Bellman equation in infinite-horizon, discrete-time, discounted, time-invariant dynamic optimization problems
  • Many string algorithms including longest common subsequence, longest increasing subsequence, longest common substring, Levenshtein distance (edit distance).
  • Many algorithmic problems on graphs can be solved efficiently for graphs of bounded treewidth or bounded clique-width by using dynamic programming on a tree decomposition of the graph.
  • The Cocke–Younger–Kasami (CYK) algorithm which determines whether and how a given string can be generated by a given context-free grammar
  • Knuth's word wrapping algorithm that minimizes raggedness when word wrapping text
  • The use of transposition tables and refutation tables in computer chess
  • The Viterbi algorithm (used for hidden Markov models)
  • The Earley algorithm (a type of chart parser)
  • The Needleman–Wunsch and other algorithms used in bioinformatics, including sequence alignment, structural alignment, RNA structure prediction.
  • Floyd's all-pairs shortest path algorithm
  • Optimizing the order for chain matrix multiplication
  • Pseudo-polynomial time algorithms for the subset sum and knapsack and partition problems
  • The dynamic time warping algorithm for computing the global distance between two time series
  • The Selinger (a.k.a. System R) algorithm for relational database query optimization
  • De Boor algorithm for evaluating B-spline curves
  • Duckworth–Lewis method for resolving the problem when games of cricket are interrupted
  • The Value Iteration method for solving Markov decision processes
  • Some graphic image edge following selection methods such as the "magnet" selection tool in Photoshop
  • Some methods for solving interval scheduling problems
  • Some methods for solving word wrap problems
  • Some methods for solving the travelling salesman problem, either exactly (in exponential time) or approximately (e.g. via the bitonic tour)
  • Recursive least squares method
  • Beat tracking in music information retrieval.
  • Adaptive-critic training strategy for artificial neural networks
  • Stereo algorithms for solving the correspondence problem used in stereo vision.
  • Seam carving (content aware image resizing)
  • The Bellman–Ford algorithm for finding the shortest distance in a graph.
  • Some approximate solution methods for the linear search problem.
  • Kadane's algorithm for the maximum subarray problem.

Read more about this topic:  Dynamic Programming

Famous quotes containing the words dynamic and/or programming:

    The nearer a conception comes towards finality, the nearer does the dynamic relation, out of which this concept has arisen, draw to a close. To know is to lose.
    —D.H. (David Herbert)

    If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.
    Melinda M. Marshall (20th century)