I need help with question 10 part a and b please. If you are going to write anyt
ID: 3602959 • Letter: I
Question
I need help with question 10 part a and b please. If you are going to write anything please make sure is neat and readable thank you. A and B are the bold text "(a)" and "(b)" I am not sure how much more clear I can be on where a and b are.
10. 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 a,>0 steps of the simulation if your job is on machine A, and b,>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 whiclh 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 andExplanation / Answer
(a) The following instance will result in a non-optimal solution:
Min 1 Min 2 Min 3
A 2 1 1
B 1 10 1
The algorithm follows the sequence a1, a2, a3 , i.e. AAA which gives a total value of 2 + 1 + 1 = 4.
Whereas the optimal sequence corresponds to BBB giving a total of 1 + 10 + 1 = 12.
(b)
Suppose we have the optimal plans for sequences upto minutes (i-2) and ending with A in the last minute. Let it be denoted by Max[A][i-2]. Similarly, we have the optimal plan till end of minute (i-1) ending with A denoted by Max[A][i-1]. Similarly for the optimal plans ending with B, Max[B][i-1] and Max[B][i-2] respectively.
Based on this we can find Max[A][i] and Max[B][i]. If the ith minute involved a MOVE from A to B or vice versa, that minute's value will not be added. If there is no move, the minute will be added to the total.
Max[A][i] = max (Max[A][i-1] + ai, Max[B][i-2])
Similarly Max[B][i] = max (Max[B][i-1] + bi, Max[A][i-2])
The optimal value for i minutes will be the maximum of Max[A][i] and Max[B][i].
The algorithm is given below:
ALGORITHM
Max[A][0] := 0, Max[B][0] := 0
Max[A][1] := ai, Max[B][1] := b1
Set i := 2
While i <= n
If Max[A][i-1] + ai < Max[B][i-2]
Max[A][i] := Max[B][i-2]
Else
Max[A][i] := Max[A][i-1] + ai
End if
Repeat the above if conditionals substituting A by B and vice-versa and replacing ai by bi.
Increment i
End while
Return max(Max[A][n], Max[B][n])
END ALGORITHM
The algorithm consists of one loop iterating from 1 to n, as it fills up the two arrays Max[A] and Max[B]. A fixed number of operations are performed in each loop iteration. Therefore the algorithm has linear time complexity, O(n).