UC Berkeley—CS 170 Problem Set 8Lecturer: Michael Jordan Due on November 3 at 3:30 p.m.Problem Set 8 for CS 170Problem 1 [Which Office Today?]Suppose that you are a professor at Berkeley and you have two offices: one in Evans Halland one in Soda Hall. Each day you choose to work in one of your two offices. Yourproductivity in Evans Hall on day i is given by the value eiand your productivity in SodaHall on day i is given by the value si. If you switch between offices on day i and i + 1, youincur a productivity loss c. Given a sequence of n days, a plan is a sequence of n locations(i.e., a sequence of choices of Evans or Soda). The productivity of a plan is the sum of theproductivities of each day minus the sum of the switching losses. The plan can begin ineither Evans or Soda. The problem is the following: Given the values {ei} and {si}, andgiven c, find a plan that maximizes your productivity.(a) Consider the greedy algorithm that chooses Evans on day i if ei> siand chooses Sodaotherwise. Give a problem instance on which this algorithm fails. (Say what the correctanswer is and why the greedy algorithm fails).(b) Give an example of a problem instance in which the optimal plan must change locationsat least three times.(c) Give an efficient algorithm that computes the productivity of an optimal plan.Problem 2 [Optimal Rebooting]You’re working for a company that runs a server that is accessed by many millions ofcustomers per day. Let’s suppose that you have an estimate of the numbers of customers(in millions) that you expect to access your server over the next n days. Denote thesevalues as (x1, x2, . . . , xn). Now the server software is not very well written, and the numberof customers that it can handle per day decreases with each day since the most recentreboot. Let sidenote the number of customers that it can handle on day i after the reboot,where we assume s1> s2> · · · > sn. If you choose to reboot on a given day, you can’tserve any customers on that day. The problem is the following: Given the expected loads(x1, x2, . . . , xn), and given the limits (s1, s2, . . . , sn), find a plan that specifies the days onwhich you will reboot the server so as to maximize the total number of customers that youserve.(a) Give an example of a problem instance with the following properties:• There is a “surplus” of customers on each day, in the sense of xi> s1for each i.• The optimal solution reboots the system at least twice. What is this optimalsolution?(b) Give an efficient algorithm that computes the number of customers served by the opti-mal plan.Problem set 8 due on November 3 at 3:30 p.m. 2Problem 3 [Triangulation]You are given a convex polygon P on n vertices in the plane (specified by their x and ycoordinates). A triangulation of P is a collection of n − 3 diagonals of P such that no twodiagonals intersect (except possibly at their endpoints). Notice that a triangulation splitsthe polygon’s interior into n − 2 disjoint triangles. The cost of a triangulation is the sum ofthe lengths of the diagonals in it. Give an efficient algorithm for finding a triangulation ofminimum cost. (Hint: Label the vertices of P by 1, . . . , n, starting from an arbitrary vertexand walking clockwise. For 1 ≤ i < j ≤ n, let A(i, j) be the minimum cost triangulation ofthe polygon spanned by vertices i, i + 1, . . . , j. Derive a dynamic program for A(i,