Question 1: (8 points) Professor Clever has designed an approximation algo- rithm ALG for the scheduling problem P||Cmax, i.e., the problem of minimizing makespan on identical parallel machines. He claims that his algorithm is a 1.5- approximation algorithm. We run ALG on some instance I with m machines and n jobs with processing times p,...,Pn. We find out that the cost (length) of the schedule found by the algorithm is more than 2 times the value , p/m (which we know is a lower bound on the optimal value.) (a) (2 points) Based on this information, can we conclude that professor Clever's claim must be false? Explain your answer. (b) (3 points) Now, the same question but with the additional information that Pj E {1,2} for each job in our instance I. (c) (3 points) Again, the same question but with the additional information that Pj E {2,3} for each job in our instance I and n 5m.