Question 1. Write a program to solve the Longest Common Subsequence problem using dynamic programming as discussed in class. For example, if the input is X = ABCBDAB and Y = BDCABA, then the output of your program should be BCBA.
Question 2. Suppose you need to create a work plan, and each week you have to choose a job to undertake. The set of possible jobs is divided into low-stress and high-stress jobs.
If you select a low-stress job in week i, then you get a revenue of li dollars; if you select a high-stress job, you get a revenue of hi dollars. The catch, however, is that in order for you to take on a high-stress job in week i, it's required that you rest in week i - 1 because you need a full week of prep time to get ready for the stress level (It's okay to choose a high-stress job in week 1.) On the other hand, you can take a low-stress job in week i even if you have done a job (of either type) in week i-1.
So, given a sequence of n weeks, a plan is speci?ed by a choice of "low-stress", "high-stress" or "none" for each of the n weeks, with the constraint that if "high-stress" is chosen for week i> 1, then "none" must be chosen for week i - 1. The value of the plan is determined in the natural way; for each i, you add li to the value if you choose "low-stress" in week i, and you add hi to the value if you choose "high-stress" in week i. (You add 0 if you choose "none" in week i.)
Example: Suppose n=4, and the values of li and hiare given by the following table. Then the plan of the maximum value would be to choose "none" in week 1, a high stress job in week 2, and low-stress jobs in weeks 3 and 4. The value of this plan would be 0+50+10+10=70.
|
i
|
Week 1
|
Week 2
|
Week 3
|
Week 4
|
|
l
|
10
|
1
|
10
|
10
|
|
h
|
5
|
50
|
5
|
1
|
Design a dynamic programming algorithm to find the value of the optimal plan. Implement your algorithm using any programming language you prefer.