This HW is on greedy algorithms. Note that for greedy algorithms, often the algorithm is

obvious$/$easy$.$ The tricky part is to prove the correctness of the algorithm, use either $$greedy stays

ahead$($e$.$g$.$ Interval Scheduling$)$ or $$exchange argument$($e$.$g$.$ Minimizing Lateness$)$ to prove.

$1.(25$ points$)$ You are planning a long hike across a desert that spans multiple oasis points. Your

hike will start at an oasis and end at another oasis, passing through several intermediary oases

along the way. Each oasis has a water refilling station. Your water bottle can hold enough

water to last for m miles, and the distance between successive oases in your hike is $<=$ m$.$

Your objective is to start your hike with a full water bottle and arrive at your destination

with the minimal number of water refilling stops. The strategy you are applying for realizing

your objective is to hike to the farthest oasis possible on the available water and then make a

refilling stop at that oasis. Prove that the strategy will indeed minimize your refilling stops.