Chapter 5 Dynamic Programming Flashcards
(13 cards)
What are the two main properties of problems suited for dynamic programming?
Optimal substructure and overlapping subproblems.
In the context of shortest-path problems, what does δ(u, v) represent?
The minimum path weight between vertices u and v.
What is the key idea behind ForwardRecursion for multi-stage graphs?
Compute shortest path lengths stage by stage using previously computed values.
Why are cycles not allowed in optimal solutions for shortest-path problems with positive weights?
Because cycles would increase the total weight, not reduce it.
What data structure does Dijkstra’s algorithm rely on for efficiency?
A priority queue.
What is the complexity of Dijkstra’s algorithm with a priority queue?
O(|E| + |V| log |V|).
What is a subsequence?
A sequence derived by deleting some elements of another sequence without changing the order of the remaining elements.
What does the LCS problem aim to find?
The longest common subsequence between two sequences.
What matrix is used to solve the LCS problem via dynamic programming?
Matrix c[i, j], storing LCS length of prefixes X1:i and Y1:j.
What does the b matrix represent in LCS algorithm?
The direction from which the LCS value was derived (←, ↑, ↖).
What is the filtering problem in HMMs?
Computing P(Xt = xt | Y1:t = y1:t), the probability of the hidden state given observed data.
How does the filtering algorithm use dynamic programming?
By storing and updating a vector mt(xt) recursively using only the previous step’s results.
What simplification is made in the filtering model?
The Markov condition: Xt depends only on Xt−1, and Yt only on Xt.
