Description

Illustrate the execution of the Coin Change algorithm on n = 10 in the system of denominations d(1) = 1, d(2) = 5, and d(3) = 8.

Pascal’s triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
…
The rst entry in a row is 1 and the last entry is 1 (except for the rst row which contains only 1), and every other entry in Pascal’s triangle is equal to the sum of the following two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.


Give a recursive de nition for the entry C[i; j] at row i and column j of Pascal’s triangle. Make sure that you distinguish the base case(s).



Give a recursive algorithm to compute C[i; j]; i j 1. Illustrate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6; 4]. Does your algorithm perform overlapping computations?



Use dynamic programming to design an O(n^{2}) time algorithm that computes the rst n rows in Pascal’s triangle.


Consider the two sequences X = hA; C; T; C; C; T; G; A; T i and Y = hT; C; A; G; G; A; C; T i of characters. Apply the Longest Common Subsequence algorithm to X and Y to compute a longest common subsequence of X and Y . Show your work (the contents of the table), and use the table to give a longest common subsequence of X and Y .

Textbook, pages 397, exercise number 15.45.

The subsetsum problem. Let S = fs_{1}; : : : ; s_{n}g be a set of n positive integers and let t be a positive integer called the target. The subsetsum problem is to decide if S contains a subset of elements
that sum to t. For example, if S = f1; 2; 4; 10; 20; 25g, t = 38, then the answer is YES because 25 + 10 + 2 + 1 = 38. However, if S = f1; 2; 4; 10; 20; 25g, t = 18, then the answer is NO. Let s = s_{1} +: : :+s_{n}.


Let T [0::n; 0::s] be a table such that T [i; s^{0} ] = S^{0} if there exists a subset of elements S^{0} in fs_{1}; : : : ; s_{i}g whose total value is s^{0} , and T [i; s^{0} ] = y otherwise; y is a ag indicating that no such S^{0} exists. Show how T [0; k] can be easily computed for k = 0; : : : ; s.


6 y
) and element s_{i} does not belong
(b) If T [i; s^{0} ] exists (T [i; s^{0} ] =
to T [i; s^{0} ], how can the value of T [i; s^{0} ] be expressed using table
entries in previous rows?
What about when T [i; s^{0} ] exists and
element s_{i} belongs to T [i; s^{0} ]? Show how entry T [i; s^{0} ] can be computed from table entries in previous rows.

Design an O(n s) time algorithm that decides if S contains a subset of elements A that sum to t.
2