Backpacking planning: You and some friends are planning a backpacking trip to the Sierras. You want to hike as far as possible each day but do not want to hike at night. On a map you have identified a large set of good camping sites. You plan to use the following system to decide where to camp each day. Each time you come to a one of the identified camp sites, you determine whether you can make to the next good site before nightfall. If you can make it to the next site before nightfall, you will continue hiking otherwise you will stop. Although there are drawbacks, e.g. you may miss staying in some great spots, you believe the system has one good feature, namely: Given that we are only hiking in the day, it minimizes the number of camping stops we will have to make. You want to determine if this claim is true or false. To model this problem, you decide to make the following assumptions. Model the trail as a long straight path of length L and assume you and your friends can hike a maximum of d miles each day. Also you check the maps and determine that the campsites are located at distances x1, x2, x3, , xn along the trail, with xi < xi+1 for all i. Also, you believe that group will always correctly determine whether or not they can reach the next campsite by nightfall. This means we can consider a set of stopping points valid if the distance between each adjacent pair is d. Thus if you stop only at the points (campsites) in a valid set you will be able to make the full trip in daylight. You know it is possible to make the full trip in daylight since the full set of campsites is valid. A. Give pseudo code that describes the (greedy) algorithm that you and your friends will use to find a valid set of campsites with the fewest number of campsites. B. Prove this algorithm always finds the optimal solution. C. Analyze the algorithms complexity.