Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSDS 310: Algorithms Assignment 5: Dynamic Programming
Problem 1
Provide a dynamic programming solution to two of the problems (of your own choice) by fol- lowing the described steps:
Steps:
(i) Identify the “last” question you need to answer in developing a solution. *(ii)* Define and prove optimal substructure.
*(vi)* Provide the pseudo code of the bottom-up procedure you use to compute the value of the optimal solution, as well as the procedure for reconstructing the optimal solution.
* Note that, you only need to apply items (ii) and (vi) on one of the problems (of your own choice, you can choose a different problem for each item). Clearly express which problems you choose.
Problems:
X = esteban and Y = stephen is 4, comprising of 1 deletion (e), 1 insertion (h), and 2 replacements (b → p and a → e). We would like to compute the edit distance between two given strings.
Problem 2
We are given n currencies and an exchange rate rij for any pair of currencies i an j. Namely, if we exchange 1 unit of currency i with currency j, we receive rij units of currency j. If we are given a source currency s and a target currency t, then we can go through a path of different currencies to reach t from s so as to maximize our profit. The markets can also charge an exchange fee depending on the number of exchanges we make. For example if the exchange fee is f(k) for making k exchanges and we start with 1 unit of currency s, then the path of exchanges s → t will yield rst − f (1) units of currency t, whereas the path of exchanges s → i → j → t will yield rsi ×rij ×rjt −f(3) units of currency t. The problem is to find the sequence of exchanges that will maximize the amount of target currency t we can obtain for a given source currency s.
(a) Define and prove the optimal substructure for this problem when there is no exchange fee (f(k) = 0 for all k).
(b) Prove that it is possible to find an exchange fee schedule f(k) so that the optimal substructure you defined above will not hold anymore.