Question 1. (10 points) Consider the following scheduling problem. There are two machines on which n jobs need to be scheduled, such that each job is scheduled on exactly one of the two machines. Job j(j=1,,n) requires pj amount of processing. Machine 1 operates at unit speed, whereas Machine 2 operates at speed s. That is, it takes pj units of time to process job j on Machine 1 and on Machine 2 this takes pj/s units of time. The goal is to assign the jobs to the machines in such a way that the time at which both machines are finished, is minimized. That is, let S1 denote the set of jobs assigned to Machine 1 and S2={1,,n}\S1 be the set of jobs assigned to Machine 2, then we want to minimizemax{jS1pj,jS2pj/s} You may assume that all pj as well as s are integral (j=1,,n). 1. Describe a dynamic programming algorithm that finds the optimal solution value (so your algorithm does not need to give the optimal assignment of jobs to the machines). Give a good description in words of the function(s) that you want to compute. Show how to initialize them, how to recursively compute their values, and where to find the optimal solution value. 2. Analyze the running time of your algorithm. Is this bounded by a polynomial in the size of the input