You are managing the construction of power plants along a river. As opposed to the last problem that involved construction along a river, this time around the possible sites for the power plants are given by real numbers x₁ ,...,x _n , each of which specifies a position along the river measured in miles from its spring. Assume that the river flows in a completely straight line. Due to differences in the water flow, the position of each power plant influences its capacity for energy production. In other words, if you place a power plant at location x_i , you will produce a quantity of electricity of r_i > 0 MW . Environmental regulations require that every pair of power plants be at least 5 miles apart. Youd like to place power plants at a subset of the sites so as to maximize total energy production, subject to this restriction. The input is given as a list of n pairs (x ₁ ,r ₁ ),...,(x _n ,r _n ) where the x _i s are sorted in increasing order. (a) Your foreman suggests some very simple approaches to the problem, which you realize will not work well. For each of the following approaches, give an example of an input on which the approach does not find the optimal solution: i. Next available location: put a power plant at i = 1. From then on, put a power plant at the smallest index i which is more than five miles from your most recently placed power plant. ii. Most profitable first: Put a power plant at the most profitable location. From then on, place a power plant at the most profitable location not ruled out by your current power plant. (b) Give a dynamic programming algorithm for this problem. Analyze the space and time complexity of your algorithm. To make it easier to present your answer clearly, try to follow the steps below (as with any design process, you may have to go back and forth a bit between these steps as you work on the problem): i. Clearly define the subproblems that you will solve recursively (note: weighted interval scheduling should be a good source of inspiration here). ii. Give a recursive formula for the solution to a given subproblem in terms of smaller subproblems. Explain why the formula is correct. iii. Give pseudocode for an algorithm that calculates the profit of the optimal solution. Analyze time/space and explain why the algorithm is correct (based on previous parts). iv. Give pseudocode for an algorithm that uses the information computed in the previous part to output an optimal solution. Analyze time/space and explain why the algorithm is correct.