DP Examples

• minimum-cost matrix-chain product: given a sequence of matrices to multiply together, what order should the intermediate products be computed to minimize the running time? (Described in book.)
• longest common subsequence: given two lists, find the largest subset of each (in order) that is the same (next time).
• longest increasing subsequence: given a list of numbers, find the largest subset (in order) that is sorted (HW).
• edit distance: given two words, how many keystrokes would it take to turn one into the other? (Useful for spelling correction and even historical linguistics, HW.)
• minimum-cost triangulation of a polygon (in book)
• TSP approximation in the plane, bitonic TSP (in book).
• shortest paths (last time, others in book).
• searching along a 1-d road
• segmentation (today)
• speech recognition: given a sequence of acoustic signals and a probabilistic model of phonemes, find the most likely phoneme (Viterbi, hidden Markov models).
• dynamic time warping: given a sequence of acoustic samples and a template model of a phoneme, find the minimum way to stretch and squeeze the sequence to fit the template.
• text alignment: given a sequence of sentences in English and their French translations and a probabilistic model relating the two languages, find the most likely way the two sequences are lined up.
• stochastic parsing: given a sentence and a stochastic grammar, find the most likely parse tree for the sentence.
• part-of-speech tagging: given a sentence and a probabilistic model of language, find the most likely part-of-speech tags for the words in the sentence.

Sequence and language related things are quite popular.