4. (10 points) You are given an integer n > 0 and k types of bills with denominations d1 = 1, d2, . . . , dk (each di is also a positive integer). Provide a dynamic programming algorithm that computes the minimum number of bills needed to make the amount n. You can assume you have infinitely many bills for each type. (Hint: While there may be many ways to approach this problem, you may start by looking at how we solved Knapsack in class. The problem here bears some similarity but is definitely simpler.)

5. (10 points) Suppose a string Z is formed by interspersing the characters from other two strings X and Y . The new string Z is called a shuffle of X and Y if characters in Z com- ing from the same string still keep the order as in the original string. For example, the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING: PRODGYRNAMAMMIINCG DYPRONGARMAMMICING Given three strings A[1..m], B[1..n], and C[1..m+n], design a dynamic programming algorithm to determine if C is a shuffle of A and B. (Hint: We have seen two problems on strings and another problem on sequences in class. Maybe you can build your ideas on what you learned from these problems.