[DPV] Practice Dynamic Programming Problems Solution

Description

Suggested reading: Chapter 6 of the book.

[DPV] Problem 6.4 { Dictionary lookup

You are given a string of n characters s[1…n],which you believe to be a corrupted text document

in which all punctuation has vanished…

[DPV] Problem 6.17 { Making-change I

Given an unlimited supply of coins of denominations x1, x2, . . . , xn, we which to make change

for a value v…

[DPV] Problem 6.18 { Making change II

Consider the following variation on the change-making problem (Exercise 6.17): you are given

denominations x1, x2, . . . , xn, …

[DPV] Problem 6.20 { Optimal Binary Search Tree

Suppose we know the frequency with which keywords occur in programs of a certain language,

for instance …

[DPV] Problem 6.26 { Alignment

Sequence alignment. When a new gene is discovered, a standard approach to understanding its

function is to look through a database of known genes and nd close matches…

Longest Common Sub*!?*

Given two strings X = x₁; x₂; : : : ; x_n and Y = y₁; y₂; : : : ; y_m give a dynamic programming algorithm to nd the length k of the longest string Z = z₁; : : : ; z_k 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:

• = a; b; d; b; a; b; f; g; d

• = 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. See next page for homework problems.

9