Problem 2 (35 points) You aim to get outside as much as possible this summer. Your two favorite activities are

hiking the White Mountains and going to the beach on Cape Cod. Each weekend you choose which

of the two activities to partake in. Hiking is your true favorite, but it is much more exhausting, so

if you go hiking one weekend, youll be too tired to get off of the couch the following one, even to

go to the beach. Your goal is to decide for each weekend whether you will go to the mountains, go

to the beach, or stay home on your couch.

For each weekend , there are non-negative values , 0 describing the value you get from

hiking or going to the beach, respectively. For each weekend, you need to output an activity

schedule from {hiking, beach, none} subject to the constraint that hiking in week must be

followed by none in week + 1. Your goal is to output a schedule of the maximum total value. For

example, given the input: ( input is shown in image)

an optimal schedule would be to go to the beach on weekend 1, hike on weekends 2 and 4, and stay

on the couch on weekend 3, which has a value of 3 + 12 + 6 = 21.

Design efficient dynamic programming for computing the optimal schedule.

2.1 Let OPT() be the maximum value you can get for partaking in these activities on weekends

, + 1, . . . , . Give a recurrence to compute OPT() from the values OPT( + 1), . . . , OPT(),

and write the base case(s) for this recurrence. Write a few sentences explaining why your

recurrence is correct.

2.2 Using your recurrence, design a dynamic programming algorithm to output the optimal

activity schedule. You may use either a top-down or bottom-up approach. Remember that

your algorithm needs to output the optimal schedule, not only its value.

2.3 Analyze the running time of your algorithm.

lem 2 (35 points) You aim to get outside as much as possible this summer. Your two favorite activities are hiking the White Mountains and going to the beach on Cape Cod. Each weekend you choose which of the two activities to partake in. Hiking is your true favorite, but it is much more exhausting, so if you go hiking one weekend, you'll be too tired to get off of the couch the following one, even to go to the beach. Your goal is to decide for each weekend whether you will go to the mountains, go to the beach, or stay home on your couch. For each weekend i, there are non-negative values hi,bi0 describing the value you get from hiking or going to the beach, respectively. For each weekend, you need to output an activity schedule from \{"hiking", "beach", "none"\} subject to the constraint that hiking in week i must be followed by none in week i+1. Your goal is to output a schedule of the maximum total value. For example, given the input: an optimal schedule would be to go to the beach on weekend 1, hike on weekends 2 and 4 , and stay on the couch on weekend 3 , which has a value of 3+12+6=21. Design efficient dynamic programming for computing the optimal schedule. 2.1 Let OPT (i) be the maximum value you can get for partaking in these activities on weekends i,i+1,,n. Give a recurrence to compute OPT (i) from the values OPT (i+1),,OPT(n), and write the base case(s) for this recurrence. Write a few sentences explaining why your recurrence is correct. 2.2 Using your recurrence, design a dynamic programming algorithm to output the optimal activity schedule. You may use either a top-down or bottom-up approach. Remember that your algorithm needs to output the optimal schedule, not only its value. 2.3 Analyze the running time of your algorithm