You're in charge of running a scientific program (job) that simulates a physical system for as many discrete steps as you can. The lab you're working in has two large supercomputers, which we'll call A and B, which are capable of processing this job. However, you're not one of the high-priority users of these supercomputers, so at any given point in time, you're only able to use as many spare cycles as these machines have available. Here's the problem you face. Your job can only run on one of the machines at any given minute. Over each of the next n minutes, you have a "profile" of how much processing power is available on each machine. In minute 1, you would be able to run a _i , > 0 steps of the simulation if your job is on machine A, and k > 0 steps of the simulation if your job is on machine B. You also have the ability to move your job from one machine to the other; but doing this costs you a minute of time in which no processing is done on your job. So, given a sequence of n minutes, a plan is specified by a choice of A, B, or "move" for each minute, with the property that choices A and B cannot appear in consecutive minutes. For example, if your job is on machine A in minute i, and you want to switch to machine B, then your choice for minute i+1 must be move, and then your choice for minute i+2 can be B. The value of a plan is the total number of simulation steps that you manage to execute over the n minutes: so it's the sum of a _i over all minutes in which the job is in A, plus the sum of b _i over all minutes in which the job is on B.

The Problem: Given values a _1, a ₂ , ?.a _n and b ₁ ,b _2? ,?.b _n find a plan of maximum value. Your plan can start at either of the machines A and B in minute 1.

Example: Suppose n = 4, and the values of a _I and b _i are given by the following table.

Then the plan of maximum value would be to choose A for minute 1 then move to minute 2, and then B for minute 3 and 4. The value of this plan would be 10+0+20+20 = 50.

(a) Let V ^A _K = the maximum value of any plan that ends at Machine A at the end of the k-th minute. Similarly, let V ^B _k = the maximum value of any plan that ends at Machine A at the end of the k-th, minute.

Write recursive formulas for V ^A _K and V ^B _k.

(b) Write an algorithm, in pseudo code, that returns the value of the best plan that ends at the n-th minute. The input to your algorithm should be integer arrays a[ ] and b[ ], where for each i= 1 to n a[i] = a _i and b[i] = b _i

A B Minute 1 10 5 Minute 2 1 1 Minute 3 1 20 Minute 4 10 20