Dynamic programming: Difference between revisions

* Many [[w:String (computer science)|string]] algorithms including [[longest common subsequence problem|longest common subsequence]]

* The [[w:CYK algorithm|Cocke-Younger-Kasami (CYK) algorithm]] which determines whether and how a given string can be generated by a given [[w:context-free grammar|context-free grammar]]

* The use of [[w:transposition table|transposition table]]s and [[w:refutation table|refutation table]]s in computer chess

* The [[w:Viterbi algorithm|Viterbi algorithm]] (used for [[w:hidden Markov model|hidden Markov model]]s)

* The [[w:Earley algorithm|Earley algorithm]] (a type of [[w:chart parser|chart parser]])

* The [[w:Needleman-Wunsch algorithm|Needleman-Wunsch]] and other [[w:sequence alignment|sequence alignment]] algorithms used in [[w:bioinformatics|bioinformatics]]

* [[w:Levenshtein distance|Levenshtein distance]] (edit distance)

* [[w:Floyd-Warshall algorithm|Floyd's All-Pairs shortest path algorithm]]

* Optimizing the order for [[w:chain matrix multiplication|chain matrix multiplication]]

* [[w:subset sum problem|Subset Sum]] algorithm

* [[w:knapsack problem|knapsack problem]]

* The [[w:dynamic time warping|dynamic time warping]] algorithm for computing the global distance between two time series

* The [[w:Selinger|Selinger]] (a.k.a [[w:System R|System R]]) algorithm for relational database query optimization

* [[w:De Boor algorithm|De Boor algorithm]] for evaluating B-spline curves

* [[w:Duckworth-Lewis method|Duckworth-Lewis method]] for resolving the problem when games of cricket are interrupted

* The Value Iteration method for solving [[w:Markov_decision_process|Markov_decision_process]]es

[[Category:Computer Science]]