1. (50 points) 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. 2. (50 points) 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 l i dollars; if you select a high- stress job, you get a revenue of h i 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 specified 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 l i to the value if you choose “low-stress” in week i, and you add h i 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 l i and h i are 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...