## Description

## Problem 1 Longest Common Sub*!?*

Given two strings X = x1, x2, . . . , xn and Y = y1, y2, . . . , ym give a dynamic programming

algorithm to find the length k of the longest string Z = z1, . . . , zk where Z appears as a substring

of X and as a subsequence of Y . Recall, a substring is consecutive elements.

For example, for the following input:

X = a, b, d, b, a, b, f, g, d

Y = b, e, t, f, d, b, f, a, f, r

then the answer is 4 (since, b, d, b, a is a substring of X and it is also a subsequence of Y). You do

not need to output the actual substring, just its length.

(Faster (and correct) in asymptotic O(·) notation is worth more credit.)

(a) Define the entries of your table in words. E.g., T(i) or T(i, j) is ….

(b) State recurrence for entries of table in terms of smaller subproblems.

Name: 3

(c) Write pseudocode for your algorithm to solve this problem.

(d) Analyze the running time of your algorithm.

Name: 4

Problem 2 [DPV] 6.17 – Coin changing (unlimited supply of each denomination)

(a) Define the entries of your table in words. E.g., T(i) or T(i, j) is ….

(b) State recurrence for entries of table in terms of smaller subproblems.

Name: 5

(c) Write pseudocode for your algorithm to solve this problem.

(d) Analyze the running time of your algorithm.