Problem 1. (20p) A lone traveler hikes in the desert. She has a single water bot

Question

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 algorithm’s 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 doesn’t 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 ?

Explanation / Answer

.

SOLUTION:

What is the running time of this method?

Well, it depends on which sorting algorihtm you use.The sorting part can be as small as O(n log n) and the other part is O(n)

, so the total is O(n log n). Theorem :

Greedy-Activity-Selector solves the activity-selection problem.

EXPLANATION :The proof is by induction on n. For the base case, let n = 1. The statement trivially holds. TYhe induction step, let n ? 2, and assume that the claim holds for all values of n less than the current one.

We may assume that the activities are already sorted according to their finishing time. Let p be the number of activities in each optimal solution for [1, . . . , n ? 1] and let q be the number for [1, . . ., n].

   Here p ? q holds.

Can you explain why? It’s because every optimal solution for [1, . . . , n ? 1] is a solution for [1, . . . , n].                       

How about the fact that p ? q ? 1?

How about the fact that p ? q ? 1?

Assume that p ? q ? 2. Let W be any optimal solution for [1, . . . , n]. Let W0 = W ? {n} if W contains n and W0 = W otherwise.

Then W0 does not contain n and is a solution for [1, . . . , n ? 1]. This contradicts the assumption that optimal solutions for [1, . . . , n ? 1] have p activities.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.