Problem 2. Armageddon The NASA Near Earth Object Program lists potential future Earth impact events that the JPL Sentry System has detected based on currently available observations. Sentry is a highly automated collision monitoring system that continually scans the most current asteroid catalog for possibilities of future impact with Earth over the next 100 years. This system allows us to predict that i years from now, there will be x tons of asteroid material that has near-Earth trajectories. In the mean time, we can build a space laser that can blast asteroids. However, each laser blast will require exajoules of energy, and so there will need to be a recharge period on the order of years between each use of the laser. The longer the recharge period, the stronger the blast-after j years of charging, the laser will have enough power to obliterate d, tons of asteroid material. You must find the best way to use the laser. The input to the algorithm consists of the vectors (x1x) and (d,d) representing the incoming asteroid material in years 1 to n, and the power of the laser d, if it charges for i years. The output consists of the optimal schedule for firing the laser to obliterate the most material. Example: Suppose (x1,x2,x3.x4) (1,10,10,1) and (di.dz.dz.d4)- (1,2,4,8). The best solu- tion is to fire the laser at times 3,4. This solution blasts a total of 5 tons of asteroids. (a) Construct an input on which the following "greedy" algorithm returns the wrong answer: Algorithm 1: The BADLASER Algorithm Compute the smallest j such that d2x, or setj-n if no such j exists Shoot the laser at time n If n>j: Return BADLASER(xi....x-j)(di...di-j) Intuitively, the algorithm figures out how many years j are needed to blast all the material in the last time slot. It shoots during that last time slot, and then accounts for the j years required to recharge for that last slot, and recursively considers the best solution for the smaller problem of sizen-j Solution: (b) Let OPT(j) be the maximum amount of asteroid we can blast from year 1 to year j. Give a recurrence to compute OPT(j) from OPT(1)., oPT(j -1). Give a few sentences justifying why your recurrence is correct. Solution: (c) Using your recurrence, design a dynamic programming algorithm to output the optimal set of times to fire the laser. You may use either a top-down or bottom-up approach. Remember that your algorithm needs to output the optimal set of times to fire the laser. Solution: Problem 2. Armageddon The NASA Near Earth Object Program lists potential future Earth impact events that the JPL Sentry System has detected based on currently available observations. Sentry is a highly automated collision monitoring system that continually scans the most current asteroid catalog for possibilities of future impact with Earth over the next 100 years. This system allows us to predict that i years from now, there will be x tons of asteroid material that has near-Earth trajectories. In the mean time, we can build a space laser that can blast asteroids. However, each laser blast will require exajoules of energy, and so there will need to be a recharge period on the order of years between each use of the laser. The longer the recharge period, the stronger the blast-after j years of charging, the laser will have enough power to obliterate d, tons of asteroid material. You must find the best way to use the laser. The input to the algorithm consists of the vectors (x1x) and (d,d) representing the incoming asteroid material in years 1 to n, and the power of the laser d, if it charges for i years. The output consists of the optimal schedule for firing the laser to obliterate the most material. Example: Suppose (x1,x2,x3.x4) (1,10,10,1) and (di.dz.dz.d4)- (1,2,4,8). The best solu- tion is to fire the laser at times 3,4. This solution blasts a total of 5 tons of asteroids. (a) Construct an input on which the following "greedy" algorithm returns the wrong answer: Algorithm 1: The BADLASER Algorithm Compute the smallest j such that d2x, or setj-n if no such j exists Shoot the laser at time n If n>j: Return BADLASER(xi....x-j)(di...di-j) Intuitively, the algorithm figures out how many years j are needed to blast all the material in the last time slot. It shoots during that last time slot, and then accounts for the j years required to recharge for that last slot, and recursively considers the best solution for the smaller problem of sizen-j Solution: (b) Let OPT(j) be the maximum amount of asteroid we can blast from year 1 to year j. Give a recurrence to compute OPT(j) from OPT(1)., oPT(j -1). Give a few sentences justifying why your recurrence is correct. Solution: (c) Using your recurrence, design a dynamic programming algorithm to output the optimal set of times to fire the laser. You may use either a top-down or bottom-up approach. Remember that your algorithm needs to output the optimal set of times to fire the laser. Solution