Question :
a) Suppose you are a marathon runner that can run a maximum of n miles on a single bottle of water. You are given a map of your marathon route with all the water stations marked. Design an efficient algorithm to determine the water stations you should fill the water at so that you make as few stops as possible. What is the time complexity of your algorithm?
b) Is the water filling problem as stated above an optimization problem or a decision problem? Why? If the water filling problem is an optimization problem, state the decision problem corresponding to the optimization problem and argue that the decision problem and the optimization problem are equivalent. Define the language corresponding to the water filling decision problem.