All algorithms are in pseudocode:

A lone traveler hikes in the desert. She has a single water bottle that allows her to walk k kms before she su ers 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 ll 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 ll 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 algorithm's running time. 1.2 (5p) Show that your algorithm is indeed nding 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 doesn't minimize the number of stops made by the traveler. Give a counter-example when the algo- rithm fails to nd the path with the minimum number of stops.

1.5 (5p) Design an algorithm that minimizes the number of stops the trav- eler 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 ?