On most clear days, a group of your friends in the Astronomy Department gets together to plan out the astronomical events theyre going to try observing that night. Well make the following assumptions about the events. . There are n events, which for simplicity well assume occur in sequence separated by exactly one minute each. Thus event j occurs at minute j; if they dont observe this event at exactly minute j, then they miss out on it.

. The sky is mapped according to a one-dimensional coordinate system (measured in degrees from some central baseline); event j will be taking place at coordinate dj, for some integer value dj. The telescope starts at coordinate 0 at minute 0. . The last event, n, is much more important than the others; so it is required that they observe event n. The Astronomy Department operates a large telescope that can be used for viewing these events. Because it is such a complex instrument, it can only move at a rate of one degree per minute. Thus they do not expect to be able to observe all n events; they just want to observe as many as possible, limited by the operation of the telescope and the requirement that event n must be observed. We say that a subset S of the events is viewable if it is possible to observe each event j S at its appointed time j, and the telescope has adequate time (moving at its maximum of one degree per minute) to move between consecutive events in S. The problem. Given the coordinates of each of the n events, find a viewable subset of maximum size, subject to the requirement that it should contain event n. Such a solution will be called optimal. Example. Suppose the one-dimensional coordinates of the events are as shown here. Event 1 2 3 4 5 6 7 8 9 Coordinate 1 4 1 4 5 4 6 7 2 Then the optimal solution is to observe events 1, 3, 6, 9. Note that the telescope has time to move from one event in this set to the next, even moving at one degree per minute. (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. Mark all events j with |dn dj| > n j as illegal (as observing them would prevent you from observing event n) Mark all other events as legal Initialize current position to coordinate 0 at minute 0 While not at end of event sequence Find the earliest legal event j that can be reached without exceeding the maximum movement rate of the telescope Add j to the set S

Update current position to be coord.~dj at minute j Endwhile Output the set S 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 the coordinates d1, d2, . . . , dn of the events and returns the size of an optimal solution.