Exercises In your example, say what the correct answer is and also what the algorithm above finds. (b) Give an efficient algorithm that takes values for a, a,..., a and b, b,, b and returns the value of an optimal plan. 11. Suppose you're consulting for a company that manufactures PC equip- ment and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply s; of equipment (measured in pounds), which has to be shipped by an air freight carrier. Each week's supply can be carried by one of two air freight companies, A or B. Company A charges a fixed rate r per pound (so it costs r. s to ship a week's supply s). Company B makes contracts for a fixed amount c per week, indepen- dent of the weight. However, contracts with company B must be made in blocks of four consecutive weeks at a time. A schedule, for the PC company, is a choice of air freight company (A or B) for each of the n weeks, with the restriction that company B, whenever it is chosen, must be chosen for blocks of four contiguous weeks at a time. The cost of the schedule is the total amount paid to company A and B, according to the description above. Give a polynomial-time algorithm that takes a sequence of supply values S1, S2, ..., S, and returns a schedule of minimum cost. Example. Suppose r = 1, c = 10, and the sequence of values is 323 Minute 1 Minute 2 Minute 3 Minute 4 A 10 1 1 10 B 5 1 20 20 Then the plan of maximum value would be to choose A for minute 1, then move for minute 2, and then B for minutes 3 and 4. The value of this plan would be 10+0+20 +20=50. (a) Show that the following algorithm does not correctly solve this problem, by giving an instance on which it does not return the correct answer. In minute 1, choose the machine achieving the larger of a, b Set i=2 While in What was the choice in minute i- 1? If A: If bi+1> ai+a+1 then Choose move in minute i and B in minute i+1 Proceed to iteration i+2 Else Choose A in minute i Proceed to iteration +1 Endif If B: behave as above with roles of A and B reversed EndWhile well.) (a) Give an example of an instance with the following properties. There is a "surplus" of data in the sense that x> s for every i. -The optimal solution reboots the system at least twice. In addition to the example, you should say what the optimal solution is. You do not need to provide a proof that it is optimal. (b) Give an efficient algorithm that takes values for x1, x2, ..., xn and S1, S2, S, and returns the total number of terabytes processed by an optimal solution. 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 which 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 and