Problem 1. Consider Exercise 6.3 in the textbook and the solution that is provided in the file Chapt6Solns.pdf, which is on Blackboard under Course Notes-Chapter6. Then consider the following problem instance:
n = 7; k = 6
m1 = 0, p1 = 4
m2 = 2, p2 = 2
m3 = 5, p3 = 7
m4 = 7, p4 = 6
m5 = 11, p5 = 5
m6 = 15, p6 = 9
m7 = 16, p7 = 3
Use the definition of P (capital P, not lowercase) provided in Chapt6Solns.pdf to solve this problem. P should be an array of length 7. First find its values. Then give the maximum expected total profit subject to the constraints and list the restaurant locations selected (i = ...).
Problem 2. Consider Exercise 6.8 in the textbook and the solution in Chapt6Solns.pdf. Then consider the following problem instance:
x = “MARKS”, y = “SHARK”
Fill in the following table of L(i,j) values as specified in Chapt6Solns:
S H A R K
M
A
R
K
S
You can see another worked example at under “Dynamic programming” at https://en.wikipedia.org/wiki/Longest_common_substring_problem,.
What is the longest common substring of “MARKS” and “SHARK”?
Finally, do the following exercises from Chapter 6. For each problem define the relevant recurrence relation along with any relevant base cases. Also, write down the top-level recurrence relation instance that needs to be solved. You do not need to write pseudocode for the resulting algorithm. Chapt6Solns.pdf has quite a few worked examples. Please write up your solutions similar to the way that those example solutions are written.
Problem 3. Exercise 6.11 Hint: Define L(i,j) = the length of the longest common subsequence between x[1,…,i] and y[1,…,j]. L(i,0) and L(0,j) are base cases.
Problem 4. Exercise 6.17 Hint: Define C(w) = true if it is possible to make change for value w with the given coin denominations. C(0) is a base case. (You may also want to consider C(w) where w is negative as a base case, depending on how you write your recurrence relation.)
Problem 5. Exercise 6.19 Hint: Define C(w,j) = true if it is possible to make change for value w with the given coin denominations, using at most j coins. The runtime should be O(vkn).
