2. 20 points There are two machines A and B and a job J. In each time interval ti of t1, .., tn, I can be executed on A by ai > 0 steps or on B by b > 0 steps or moved between machines (from A to B or from B to A, J is executed 0 step). Design an O(n) time dynamic programming algorithm (structure of optimal solution, Bellman equation, pseudo code) which, given ai, ... An and b1, .., bn, computes a plan that decides run J on A or on B or move between machines for every interval such that J is executed by a maximum number of steps. At ti, J can be executed on either A or B. Your algorithm should compute both the maximum number of steps and the plan to achieve the maximum number of steps. 2. 20 points There are two machines A and B and a job J. In each time interval ti of t1, .., tn, I can be executed on A by ai > 0 steps or on B by b > 0 steps or moved between machines (from A to B or from B to A, J is executed 0 step). Design an O(n) time dynamic programming algorithm (structure of optimal solution, Bellman equation, pseudo code) which, given ai, ... An and b1, .., bn, computes a plan that decides run J on A or on B or move between machines for every interval such that J is executed by a maximum number of steps. At ti, J can be executed on either A or B. Your algorithm should compute both the maximum number of steps and the plan to achieve the maximum number of steps