Suppose you run a company with two offices, one in Washington, D$.$C$.$ and the other in San Francisco,

Claifornia. You always spend the whle week in one location, but each weekend, you decide whether

to fly to the other office. In week $i,$ you can make $W_i$ dollars if you are in Washington, and $C_i$

dollars if you are in Calfiornia. Each flight from one office to the other costs $1000.$ Suppose you are

initially in D$.$C$.,$ and you are given the lists of potential profits for each location: $W_1,W_2,$dots,$W_n$ and

$C_1,C_2,$dots,$C_n.$ Additionally, you are given $L_{f}in\{C,W\},$ your final location which is the location that

you must be in after the $n$th week. This means if you spent the $n$th week in California, and $L_f=W$

you must spend a final $$1000$ to fly back at the end of the $n$th week. In this problem, you will come

up with an algorithm to maximize your profit.

$($a$)$ A greedy algorithm would look at how much money you would make in each week, and work in

the place that will earn the most that week $($after travel costs$).$ Give a counter example to show

why this greedy algorithm is not always optimal. $($Your example should have $n3,$ otherwise a

later part of this problem will be more challenging.$)$

$($b$)$ Create a dynamic programming algorithm to solve this problem. I will guide you through the

steps

i$.$ Identify the likely subproblems and recurrence objects. $($Ilint: you need two sequences of

subproblems, depending on whether you have to end up in DC or California$)$

ii$.$ Determine the relevant final options for the recurrence object and write a recurrence relation

for your recurrence object for each option. Also determine base case$($s$).$ Briefly explain.

iii. Turn your recurrence relation for your recurrence object into a recurrence relation for the

objective function value.

iv$.$ Fill in pscudocode for an algorithm to determine the optimal schedule.

$($c$)$ What is the runtime of your algorithm?

$($d$)$ Apply your algorithm to your example from part $($b$)$ and show that it outputs the correct

schedule.