Problem 1. (20p) A lone traveler hikes in the desert. She has a single water bottle that allows her to walk k kms before she suffers from dehydration. She has a map of the n water-holes that are scattered along the desert, and can plan her hike in advance, especially the places where she stops to fill her bottle.

1.1 (5p) Assume she hikes on a single clear path (i.e., the desert is 1- dimensional). The greedy algorithm where she stops along the furthest reachable waterhole to fill her bottle is the one that minimizes the number of stops. Describe how to implement this greedy algorithm in O(n log(n)) time. Prove your algorithms running time.

1.2 (5p) Show that your algorithm is indeed finding the optimal path with minimum number of stops by proving its optimal substructure property and its substitution property

1.4 (5p) Show that if she hikes in the wilderness (i.e., the desert is 2- dimensional) then the greedy algorithm doesnt minimize the number of stops made by the traveler. Give a counter-example when the algorithm fails to find the path with the minimum number of stops.

1.5 (5p) Design an algorithm that minimizes the number of stops the traveler makes regardless of the desert being 2-dimensional, 3-dimensional (a space traveler) or through any other metric. What is the running time of your algorithm ?