Categories

# Algorithms (Dynamic Programming)

1. On a clear day, a group of your friends in the Astronomy club gets together to plan outthe astronomical events theyre going to try…

1. On a clear day, a group of your friends in the Astronomy club gets together to plan outthe astronomical events theyre going to try observing that night. Well make thefollowing assumptions about the events.
– There are n events, which for simplicity well assume occur in sequence separated byexactly one minute each. Thus event j occurs at minute j; if they dont observe thisevent at exactly minute j, then they miss out on it.
– The sky is mapped according to a one-dimensional coordinate system (measured indegrees from some central baseline); event j will be taking place at coordinate dj , forsome 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 theyobserve event n.
The Astronomy club 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 perminute. Thus they do not expect to be able to observe all n events; they just want toobserve as many as possible, limited by the operation of the telescope and therequirement that event n must be observed. We say that a subset S of the events isviewable if it is possible to observe each event j S at its appointed time j, and thetelescope has adequate time (moving at its maximum of one degree per minute) to movebetween consecutive events in S.
The problem: Given the coordinates of each of the n events, find a viewable subset ofmaximum size, subject to the requirement that it should contain event n. Such a solutionwill 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 -2
Then the optimal solution is to observe events 1, 3, 6, 9. Note that the telescope has timeto move from one event in this set to the next, even moving at one degree per minute.
Give a dynamic programming algorithm that takes values for the coordinates d1, d2,, dn of the events and returns the size of an optimal solution. Note that you need to:
(1) write the iterative version of the algorithm to find the maximal size.(2) show the algorithm for tracing the events selected.(3) give a brief argument of correctness, and(4) analyze the running time.
2. A complex linear structure is to be assembled out of n smaller pieces. We will think ofeach piece as an interval [a; b]. The joining operation takes [a; b] and [b; c] and produces[a; c]. After joining, each subpart must be tested. Assume that the cost to test [u; v] isgiven by f(u; v) > 0.
Different assembly orders potentially have different total testing cost. For example,suppose that we have three pieces corresponding to intervals [1; 2]; [2; 3]; and [3; 4], andthe cost of testing is given by: f(1; 3) = 3, f(2; 4) = 1, and f(1; 4) = 5. Then assembling the first and second pieces first and then joining them with the third has a total testing cost of f(1; 3) + f(1; 4) = 8, whereas assembling the second and third pieces first and then joining them with the first has a total testing cost of f(2; 4) + f(1; 4) = 6. Therefore, the second assembly order is preferable.
Design an O(n3) algorithm using dynamic programming methodology to find an optimal(least total testing cost) assembly order. Note that you should:
(1) use iterative implementation for the algorithm to find the optimal cost, and(2) Show the algorithm for finding the optimal order.(3) give a brief argument of correctness, and(4) analyze the running time. 