1 Exercises for DP Algorithms on Sequences
Given A = {1, 4, 2, 9, 7, 5, 8, 2}, find the longest increasing subsequence (LIS) Show your work: the filled dynamic programming table and how the solution is found.
2 Coin change
We revisit the coin change problem. Here, we have four types of coins: half-dollar (50 cents), quarter, dime and penny. We assume each coin has unlimited supply. Recall the objective is to give the smallest number of coins to change for n cents.
1. In this problem, will the greedy algorithm give optimal solution? Justify your answer.
2. Give a dynamic programming algorithm for the more general problem, where we have coins worthing d1, d2, . . . , dk (where d1 = 1, the penny). Use the following definition for your algorithm: C [i, w] is equal to the smallest number of coins for choosing coins of d1, d2, . . . , di only for making change of w cents.
3. Now suppose the government just issues a new one dollar coin. You only have one coin of one- dollar (the other coin types are still of unlimited supply). You are lazy: you do not want to design a new algorithm, but rather you want to re-use the algorithm in the previous step. Now tell me how you can solve this slightly changed problem (where you can use the single $1 coin) with the algorithm in the previous step (i.e. algorithm without knowing about the one $1 coin).
3 Longest common subsequence (LCS)
Show the dynamic programming table of the longest common subsequence problem for two sequences:
S1 = ABAABBA and S2 = BAAABAB. Also show how to find the LCS itself from the table.
4 Exercise 2(b)
Do Exercise 2(b) of your textbook on page 313.
