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 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
