On most clear days, a group of your friends in the Astronomy Departmentgets together to plan out the astronomical events they’re going to try observing that night. We’ll makethe following assumptions about the events:• There are n events, which for simplicity we’ll assume occur in sequence separated by exactly oneminute each. Thus event j occurs at minute j; if they don’t observe this event at exactly minutej, then they miss out on it.• The sky is mapped according to a one-dimensional coordinate system (measured in degrees fromsome 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 observeevent 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. Thusthey 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 saythat a subset S of the events is viewable if it is possible to observe each event j ∈ S at its appointedtime j, and the telescope has adequate time (moving at its maximum of one degree per minute) tomove between consecutive events in S. Notice that you can move either forward or backwards.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 9Coordinate 1 -4 -1 4 5 -4 6 7 -2Then the optimal solution is to observe events 1, 3, 6, 9. Note that the telescope has time to movefrom one event in this set to the next, even moving at one degree per minute.

(a) Show that the following greedy algorithm does not always correctly solve this problem, by givingan instance on which it does not return the correct answer. Show an example where the correctanswer is not returned, and say what it should be. (Notice that it actually returns the correctanswer in the example above, but show an example where it doesn’t. You can start from theexample above and modify it a little).• Mark all events j with |dn − dj | > n − j as illegal (as observing them would prevent you fromobserving 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• Output the set S

(b) Give a dynamic programming algorithm that takes values for the coordinates d1, d2.....dn of theevents and returns the size of an optimal solution.Hint: Notice that the notion of legal events is still needed here, and it can be applied to any twoevents i and j such that i < j. In other words, if |dj − di| > j − i, you can’t reach event j afterevent i.Another hint: First think of a recursive solution to the algorithm (that is – you know you haveto include event n, so you should find the optimal solution for the legal events before n and attachn to it. Recursively, this applies to the rest of the events. Flesh it out.

Answer rating: 100% (QA)

a The greedy algorithm does not always correctly solve this problem For example if the c... View the full answer