Friday, 11 January 2013
Question 1: Marks 10
After reviewing the activity scheduling with greedy approach, suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is greedy algorithm and prove that it yields an optimalsolution.
Question 2: Marks 10
Mr. Mohsin drives a car from Lahore to Rahim Yar Khan along National Highway, His car’s gas tank, when full, holds enough gas to travel n miles, and his map gives the distance between gas station on his route. Mohsin wishes to make as few gas stops as possible along the way.
Give an efficient method by which Mohsin can determine at which gas stations he should stop, and prove that your strategy yields an optimal solution.
After reviewing the activity scheduling with greedy approach, suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is greedy algorithm and prove that it yields an optimalsolution.
Question 2: Marks 10
Mr. Mohsin drives a car from Lahore to Rahim Yar Khan along National Highway, His car’s gas tank, when full, holds enough gas to travel n miles, and his map gives the distance between gas station on his route. Mohsin wishes to make as few gas stops as possible along the way.
Give an efficient method by which Mohsin can determine at which gas stations he should stop, and prove that your strategy yields an optimal solution.
