Greedy Algorithm (15 points) In a lawn, there are n lawn sprinklers S1,...,Sn installed on the center line of the lawn. Every sprinkler sprays D meters long in the same fixed direction from east to west. The sprinkler S1 is at the east borderline of the lawn. Each sprinkler Si (2 i n) is di D meters away from the previous sprinkler Si1. The sprinkler Sn is at the west borderline of the lawn. What is the minimum number of sprinklers you must open to cover the lawn from its east side to its west side? a) Design an algorithm (you can provide a pseudo-code) that solves the above optimization problem. (6 points) b) What is the asymptotic running time of your algorithm in terms of n? (2 points) c) Prove the correctness of your algorithm. (8 points)