08-02-2017, 09:34 AM

CS502 Fundamentals of Algorithms GDB Solution

GDB Question

Scenario

Solution

I think Bellman-Ford algorithm will suffice this problem. As it is a directed graph with non-negative weights problem, Bellman-Ford algorithm has the best time complexity for it, which is O(VE) [Big O of (VE)]

GDB Question

Scenario

Suppose you were to drive from Lahore to Islamabad along I-70. Your Petrol tank, when full, holds enough petrol to travel m miles, and you have a map that gives distances between petrol stations along the route. Let c1 < c2 < . . . < cn be the locations of all the petrol stations along the route where ci is the distance from Lahore to the petrol station. You can assume that the distance between neighboring petrol stations is at most m miles. Your goal is to make as few petrol stops as possible along the way.

Point of Discussion:

Keeping in view the above scenario, you need to answer the following question:

Which is the most efficient algorithm you can find to determine the petrol station you should stop? Justify your answer with solid reasoning.

Moreover specify the time complexity of the algorithm.Solution

I think Bellman-Ford algorithm will suffice this problem. As it is a directed graph with non-negative weights problem, Bellman-Ford algorithm has the best time complexity for it, which is O(VE) [Big O of (VE)]