Assignment #3 Solution

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 col-umn 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. Illus-trate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6; 4]. Does your algorithm perform over-lapping computations?


Use dynamic programming to design an O(n2) 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.4-5.



The subset-sum problem. Let S = fs1; : : : ; sng be a set of n positive integers and let t be a positive integer called the target. The subset-sum 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 = s1 +: : :+sn.




Let T [0::n; 0::s] be a table such that T [i; s0 ] = S0 if there exists a subset of elements S0 in fs1; : : : ; sig whose total value is s0 , and T [i; s0 ] = y otherwise; y is a ag indicating that no such S0 exists. Show how T [0; k] can be easily computed for k = 0; : : : ; s.
6 y
) and element si does not belong
(b) If T [i; s0 ] exists (T [i; s0 ] =


to T [i; s0 ], how can the value of T [i; s0 ] be expressed using table
entries in previous rows?
What about when T [i; s0 ] exists and
element si belongs to T [i; s0 ]? Show how entry T [i; s0 ] 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