Assignment #3 Solution

$30.00 $24.90

Description

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

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

    1. 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).

    1. 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?

    1. Use dynamic programming to design an O(n2) time algorithm that computes the rst n rows in Pascal’s triangle.

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

  1. Textbook, pages 397, exercise number 15.4-5.

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

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

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

2