CODING PART -cs6515 Dynamic Programming Homework Solution -VIEW
Suggested reading
Chapter 6 [DPV]
Practice Problems
(Do not turn these in; Model solutions will be made available on Thursday)
[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.8 – Longest common substring
Given two strings x = [1…n] and y = [1…m] we wish to find the length of their longest common substrings…
[DPV] Problem 6.18 – Making change II
Consider the following variation on the change-making problem (Exercise 6.17): you are given denominations
𝑥1,𝑥2,…,𝑥𝑛
, …
[DPV] Problem 6.19 – Making change k
Given an unlimited supply of coins of denominations
𝑥1,𝑥2,…,𝑥𝑛
, we wish to make change for a value v using at most k coins…
[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 find close matches
Graded Problem
(You will submit your solution to this Problem in Gradescope)
Famous Carribean pirate Captain Brittus is in front of the lost treasure of Conqueror Diego Velazquez. The treasure consists of a row of n chests, each with an amount of golden coins. BUT, some chests carry an ancient curse.
Luckily, Brittus has a map Diego himself left with the amount of gold in each chest, the locations of the cursed chests, and a way to get rid of them: you must pair each cursed chest with exactly one of its neighbors, making both disappear, along with their gold.
Once Brittus gets rid of all the cursed chests, he can keep all the gold in the remaining chests. Help the pirate figure out the maximum amount of gold he can get!
You are given a sequence of chests G of length n, where the entry G[i] represents a non-negative amount of gold inside the ith chest. If G[i] = 0, then it is a cursed chest.
Example: G = [2, 1, 0, 3, 5], then the maximum gold you can get is 10. Because the third chest is cursed, you optimally vanquish the chest to its left and keep the remaining ones.
Develop an efficient dynamic programming algorithm to return the maximum amount of gold in the chests that remain after all cursed chests have been vanquished along with the positions of the remaining chests.
Notes:
- It is always possible to remove every cursed chest.
Please answer the following parts:
- Define the entries of your table in words. E.g. T(i) or T(i, j) is …
- State a recurrence for the entries of your table in terms of smaller subproblems. Don’t forget your base case(s).
