[DPV] Practice Dynamic Programming Problems Solution

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 = x1; x2; : : : ; xn and Y = y1; y2; : : : ; ym give a dynamic programming algorithm to nd 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:

    • =  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.


 
Problem 1    [DPV] Problem 6.1 { Maximum sum

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S...

    (a) De ne 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.


 

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

    (d) Analyze the running time of your algorithm.


 
Problem 2    [DPV] Problem 6.8 { Longest common substring

Given two strings x = x1x2 : : : xn and y = y1y2 : : : ym we wish to nd the length of their longest common substrings...

    (a) De ne 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.

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

 
    (d) Analyze the running time of your algorithm.

 
Problem 3    [DPV] Problem 6.19 { Making change k

Given an unlimited supply of coins of denominations x1; x2; :::; xn, we wish to make change for a value v using at most k coins...

    (a) De ne 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.


 
 
    (c) Write pseudocode for your algorithm to solve this problem.
 
    (d) Analyze the running time of your algorithm.



 
Problem 4    (The thief’s plan)

A thief is planning on burglarizing some subset of n consecutive houses in a neighborhood. The houses are labeled 1; 2; : : : ; n and the thief will address then sequentially. The thief has an estimate of the pro t to be earned from burglarizing each house pi; i = 1 : : : n, where pi > 0. To avoid de-tection, he decides that he will never burglarize two adjacent houses, meaning that if he burglarize house 2, he cannot burglarize house 1 or house 3. Design a dynamic programming algorithm to determine the maximum total pro t he can achieve.

Example: In each of the following two neighborhoods, the maximum achievable pro t is $100:

Case 1: p = [$20; $100; $30].

Case 2: p = [$40; $30; $10; $60].

Your input is the list [p1; p2; : : : ; pn]. Your output should be the maximum pro t the thief can get. You don’t have to return the list of houses the thief has to burglarize to achieve the maximum.

    (a) De ne 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.


 

    (c) Write pseudocode for your algorithm to solve this problem.
 
    (d) Analyze the running time of your algorithm.




 

9