1. There is a long, straight pipeline with critical monitoring devices attached to it that you want to be able to be able to repair in an emergency. In order to be able to repair them there needs to be an access road that runs up to the pipeline and is within 2 miles (comfortable walking distance) along the pipeline of each monitoring device. Suppose the monitoring devices are at integer distances m(1), ,m(n) from the beginning of the pipeline. Assume that m(i) < m(i+1) for all i from 1 to n-1. You want to determine the number and locations of the access roads that you have to build and maintain. Since the access roads are very expensive you want to build the smallest number of access roads possible. a. How does your algorithm determine where the next road is placed. A simple one line description but be specific. No pseudo code required.
2. b. Explain briefly why your algorithm is O( number of devices).
3. c. Prove your algorithm always finds the optimal solution. Use the notation DG[j] for the j the device location chosen by the greedy algorithm and D*[j] for a presumed optimal solution.