Question

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 i you would be able to run ai> 0 steps of the simulation if your job is on machine A, and b, > 0steps 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 ai over all minutes in which the job is in A, plus the sum of b over all minutes in which the job is onB The Problem: Given values a,a an and b,b. .bn find a plan of maximum value. Note that your plan can start at either of the machines A and B in minute 1. Example: Suppose n 4, and the values of a, and bi are given by the following table. Minute 1 10 Minute 2 Minute 3 Minute 4 10 20 20 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) [10 pts Letthe maximum value of any plan that ends at Machine A at the end of the k-th minute Similarly, letthe maximum value of any plan that ends at Machine A at the end of the k-th minute. Write recursive formulas for and (b) [10 pts] 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 bl1, where for eachi- 1ton, old a and

Answer 1

a.) let V(A,k) denote the maximum value of any plan that ends at machine A at the end of kth minute and let V(B,k) denote the maximum value of any plan that ends at machine B at the end of kth minute.

Now, if any plan ends at machine A at the end of kth sec, then at the end of k-1th second, it could be at machine A or machine B. if there is a simple shift from machine A at the end of k-1th sec to machine A itself, then a[k] is added to the max value plan and if there is a move from machine B to machine A at the end of k-1th sec, then the max value plan remains same(equal to max value plan after k-1th sec) after the kth sec as well since kth sec is utilized in moving.

Hence, we can derive the recurrence relation from this observation as below:-

V(A,k) = max( V(A,k-1) + a[k], V(B,k-1) )

similar explanation can be given for V(B,k) as well and thus the recurrence relation would be

V(B,k) = max( V(B,k-1) + b[k], V(A,k-1) )

  

b.) pseudo code for finding max value plan after nth sec:-

###this is a recursive code:-

max_plan(a[ ], b[ ], n){

// this is base case. if n = 1, it tells that we are at starting point and need to choose the max value from a[1] and b[1]

if( n == 1 ){

return max( a[1], b[1] )

}

// recursive calls

max_A = max( max_plan(a[ ], b[ ], n-1) + a[n], max_plan(b[ ], a[ ], n-1)

  max_B = max( max_plan(b[ ], a[ ], n-1) + b[n], max_plan(a[ ], b[ ], n-1)

// final result

return max( max_A, max_B )

}