Homework 4 - More Dynamic Programming
The homework is due at the start of class on Tuesday, April 7.
Please write your dynamic programming solutions in the following form:
- Part (a), define the entries of the table in words,
-
e.g., T(i) = min cost subsequence of items a1,...,ai
or
-
T(i,j) = TRUE if there is a subsequence of items a1,...,ai which sums to j,
-
and FALSE otherwise.
-
Part (b), state the recurrence for the entries of your table,
and, if necessary, explain in words why it's true.
-
Part (c), state pseudocode for filling the table,
and
- part (d), analyze the running time.
- Longest common substring: [DPV] Problem 6.8.
- Coin changing (with unlimited supply): [DPV] Problem 6.17
- Coin changing (use each denomination once): [DPV] Problem 6.18
- Sequence alignment: [DPV] Problem 6.26.
You only need to output the maximum score obtainable from an alignment, you
don't need to output the actual alignment.
Also, to make it simpler you can assume the alphabet is of size 4 corresponding to
{A,C,G,T}.
An example of a simple scoring matrix δ is the following:
1
= δ(A,A)
= δ(C,C)
= δ(G,G)
= δ(T,T).
.75
= δ(A,G)
= δ(G,A).
= δ(C,T)
= δ(T,C)
.2
= δ(A,C)
= δ(A,T)
= δ(T,A).
= δ(T,G).
= δ(C,A)
= δ(C,G)
= δ(G,C)
= δ(G,T)
.1
= δ(A,-)
= δ(-,A)
= δ(T,-).
= δ(-,T).
= δ(C,-)
= δ(-,C)
= δ(G,-)
= δ(-,G)
But your algorithm should work for any 5x5 matrix δ
that is given as input.
- Palindrome substring:
Similar to [DPV] Problem 6.7, but substring instead of subsequence.
So given a string X=x1...xn,
give an O(n2) time algorithm
to determine the
length of the longest substring of X which is a palindrome.
- Optimal binary search tree: [DPV] Problem 6.20