1. Consider the following coin changing problem. You are given a value N and an infinite supply of coins with values d1, d2, . . . , dk. Give an O(Nk) algorithm for finding the smallest number of coins that add up to the value N.
2. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements; e.g. "ace?' is a subsequence of "abcdef." Consider the problem of finding the longest common subsequence of two sequences - this is a task versioning systems like git or cvs often solve. Show that this is a special case of the sequence alignment problem. Then, give a polynomial-time algorithm for finding the longest subsequence common to three sequences. Analyze its running time and argue why it is correct.
3. String C is considered to be an interleaving of strings A and B if it contains all (and only) the characters of both A and of B and their respective order is preserved in C. For example, C = aacabbaa is an interleaving of A = aaba and B = caba (demonstrated as follows: aacabbaa). Give an algorithm that, given strings A, B, and C, decides whether C is an interleaving of A and B in polynomial time. Prove your answer correct.
4. What would it mean to add memoization to Strassen's matrix multiplication algorithm?
What asymptotic improvement (if any) does it yield in the worst case? Explain your answer.