1 - Biola University



Test 5: Dynamic Programming

Due: Wednesday, Dec. 14

1. Given an unlimited supply of 5¢, 4¢, 1¢ stamps and an amount of N¢, we want to use the minimum number of stamps possible totaling to the amount of N¢.  (i) First, give a counterexample to show that the greedy approach of using as many stamps of 5¢ stamps, then 4¢ stamps, and then 1¢ stamps fails to solve this problem. (ii) Devise an O(N) time dynamical programming algorithm to solve the problem. (iii) Analyze the running time of your algorithm and show that it is indeed an O(N) time algorithm. (iv) Show how you can apply your algorithm to choose the minimum number of stamps totaling to the amount of 23¢.  

2. Suppose you are given three strings of English letters X = x1x2…xM, Y = y1y2…yN, Z = z1z2…zm+n. The string Z is a shuffle of X and Y if and only if Z can be formed by interspersing the characters from X and Y in a way that preserves the left-to-right ordering of the characters from X and Y respectively. For example, cchocohilaptes is a shuffle of chocolate and chips, but chcccochilatspe is not. (i) Devise an O(MN) time dynamical programming algorithm that can always correctly determine whether Z is a shuffle of X and Y given any strings X,Y, and Z. (ii) Analyze the running time of your algorithm and show that it is indeed an O(MN) time algorithm. (iii) Demonstrate concretely how you can apply your algorithm to determine whether chocochilatspe is a shuffle of chocolate and chips. 

3. Consider the instance of the (0/1) knapsack problem below. Apply the dynamic programming algorithm described in reading #14 to determine what items to select to maximize the total value of the selected items. What are the items selected? What is the maximum total value?

|Knapsack Capacity is 10. Five items below |

|Item |Value |Weight |

|1 |7 |2 |

|2 |12 |3 |

|3 |20 |4 |

|4 |28 |5 |

|5 |30 |6 |

4. Consider the RNA sequence AAGCGACGUU. Apply the dynamic programming algorithm described in reading #14 and also in the slide for the RNA secondary structure programming assignment to determine the maximum number of base pairs possibly formed in the RNA sequence. What is the maximum number of base pairs possibly formed? Show a way of having this number of base pairs formed in the RNA.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download