1. 10 marks] Suppose you are scheduling jobs in a factory to maximize profit. In the ith week, you can choose not to do any job, do an easy job with profit e20, or do a hand job with proft 0. In order to do a hard job, you must use all your manpower to gather resources for it in the previous week. That is, if you wish to do a hard job in week i, then you must choose not to do any job in week i -1. If you do an easy job in week i, then you are free to do any type of job (or no job at all) in week i - 1 Your task is to come up with a schedule of the jobs to be done in each week (i.e. choose among the easy job for this week, the hard job for this week, or no job), so that the total profit is maximized. A greedy algorithm is to compare h2 with e +e2. If h2 is larger, then do not do any job in week 1 and do the hard job in week 2. Otherwise, do easy jobs in both week 1 and week 2. Then consider h4 and use the same strategy, and so on. This will schedule jobs for all the weeks if n is an even number. If n is an odd number, then after scheduling all the weeks up to and including week n -1, do an easy job in week n. Give a counterexample to show that this greedy algorithm will not always yield an optimal solution. Argue carefully why it is a counterexample