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 onedollar (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.
