You are planting tomato plants in a garden, and the garden has n spots arranged in...

Transcribed Image Text:

You are planting tomato plants in a garden, and the garden has n spots arranged in a line. Different spots in the garden will result in different quality tomatoes: suppose that the location i will result in tomatoes of deliciousness T[i], where T[i] is a positive integer. Further, you cannot plant two plants directly next to each other, because they will compete for resources and wilt. Your goal is to create the most deliciousness possible (summed up over all of the tomato plants). For example, if the input was T = [21, 4, 6, 20, 2, 5], then you should plant tomatoes in the pattern and you would obtain deliciousness 21 +20 +5 = 46. You would not be allowed to plant tomatoes in the pattern because there are two tomato plants next to each other. In this question, you will design a dynamic programming algorithm which runs in time O(n) which takes as input the array T and returns the maximum deliciousness possible given T. Do this by answering the two parts below. (a) (3 pt.) What sub-problems will you use in your dynamic programming algorithm? What is the recursive relationship which is satisfied between the sub-problems? What is the base case for this recursive relationship? [We are expecting: ] A clear description of your sub-problems. . A recursive relationship that they satisfy, along with a base case. . An informal justification that the recursive relationship is correct. (b) (3 pt.) Write pseudocode for your algorithm. Your algorithm should take as input the array T, and return a single number which is the maximum amount of deliciousness possible. Your algorithm does not need to output the optimal way to plant the tomatoes. [We are expecting: Pseudocode AND a clear English description. You do not need to justify that your algorithm is correct, but correctness should follow from your reasoning in part (a).] You are planting tomato plants in a garden, and the garden has n spots arranged in a line. Different spots in the garden will result in different quality tomatoes: suppose that the location i will result in tomatoes of deliciousness T[i], where T[i] is a positive integer. Further, you cannot plant two plants directly next to each other, because they will compete for resources and wilt. Your goal is to create the most deliciousness possible (summed up over all of the tomato plants). For example, if the input was T = [21, 4, 6, 20, 2, 5], then you should plant tomatoes in the pattern and you would obtain deliciousness 21 +20 +5 = 46. You would not be allowed to plant tomatoes in the pattern because there are two tomato plants next to each other. In this question, you will design a dynamic programming algorithm which runs in time O(n) which takes as input the array T and returns the maximum deliciousness possible given T. Do this by answering the two parts below. (a) (3 pt.) What sub-problems will you use in your dynamic programming algorithm? What is the recursive relationship which is satisfied between the sub-problems? What is the base case for this recursive relationship? [We are expecting: ] A clear description of your sub-problems. . A recursive relationship that they satisfy, along with a base case. . An informal justification that the recursive relationship is correct. (b) (3 pt.) Write pseudocode for your algorithm. Your algorithm should take as input the array T, and return a single number which is the maximum amount of deliciousness possible. Your algorithm does not need to output the optimal way to plant the tomatoes. [We are expecting: Pseudocode AND a clear English description. You do not need to justify that your algorithm is correct, but correctness should follow from your reasoning in part (a).]