You're trying to run a large computing job in which you need to simulate 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 in 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 i, you would be able to run ai > 0 steps of the simulation if your job is on machine A, and bi > 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 steps that you manage to execute over the n minutes: so it's the sum of ai over all minutes in which the job is on A, plus the sum of bi over all minutes in which the job is on B
The problem. Given values a1, a2, an and b1, b2, bn, find a plan of maximum value (Such a strategy will be called optimal.) Note that your plan can start with either of the machines A or B in minute1
Example. Suppose n = 4, and the values of ai and bi are given by the following table. Minute 1 Minute 2 Minute 3 Minute 4 A 10 B 5 20 20
Then the plan of maximum value would be to choose A for minute 1, then move for minute 2, and then B for minutes 3 and 4, The value of this plan would be 10 + 0 + 20 + 20 = 50
(a) Show that the following algorithm does not correctly solve this problem, by giving an instance on which it does not return the correct answer In minute 1, choose the machine achieving the larger of a bi Set 1-2 While n what was the choice in ninute-1? If A: If bHi> ata then Choose move in ninute f and B in ninute +1 Proceed to iteration +2 Else Choose A in minute i Proceed to iteration +1 Endif If B: behave as above vith roles of A and B reversed Endwhile In your example, say what the correct answer is and also what the algorithm above finds
(b) Give an efficient algorithm that takes values for a1, a2, ,an and b1, b2, … ,bn and returns the value of an optimal plan.