We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

www.vustudents.ning.com

cs502 GDB solution

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 questions:

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.

Best of Luck!

..How to Join Subject Study Groups & Get Helping Material?..

Views: 2625

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Replies to This Discussion

Our main purpose here discussion not just Solution

We are here with you hands in hands to facilitate your learning and do not appreciate the idea of copying or replicating solutions. Read More>>

Note:-

For Important Helping Material related to this subject (Solved MCQs, Short Notes, Solved past Papers, E-Books, FAQ,Short Questions Answers & more). You must view all the featured Discussion in this subject group.

For how you can view all the Featured discussions click on the Back to Subject Name Discussions link below the title of this Discussion & then under featured Discussion corner click on the view all link.

&

.... How to Find Your Subject Study Group & Join ....

P.S:    Please always try to add the discussion in proper format title like “CS101 Assignment / GDB No 01 Solution & Discussion Due Date: ___________”

idea

Greedyalgorithm is suitable for this scenario. Because Greedyalgorithm or measuring algorithm follows the problem solving heuristic of making the locally optimal choice at each stage  for finding a global optimism. For optimal solution Greedy algorithm takes unreasonably steps like divide and conquer, mathematical optimization, randomizedalgorithm. He solves combinatorial problems with properties of matriodes.

Time complexity:

Complete with variables current Time and Number of station.

Current time = 55

Number of station = cs1, cs2…..cs4.

Current time = number of station

55 - 30 =   25     cs1 away from Lahore 30 mints

25 - 15 = 10     cs2 away from Lahore 30+15 mints

10 - 5 =    5       cs3 away from Lahore 30+15+5 mints

5 - 5 =       3      cs4 away from Lahore 30+15+5 + 5 mints

how is current time = 55 ? plz koi explain b krdey ye

Yaar ye algorithm Dijkstra nahi hoga?? or yeh time suppose kiya hai ya kisi link se copy kiya hai...

mujh bhi ya dijkstra algorithm hi lag raha ha.

solution?

please koi yehi bta de k ye topic konsey chapter main se aya hai ????

ACTIVITY SELECTION ALGORITHM MAIN SY

Pura toh nahi per kuch help yahan se mil sakti hai,, look at problem statement,, see the link below               http://people.cs.ksu.edu/~subbu/Papers/Minimum%20Stops.pdf

Latest Activity

Sadia Awan joined + M.Tariq Malik's group

ENG518 Research Methodology in ELT

12 minutes ago
Sadia Awan, zobialatif, Tehseen and 2 more joined Virtual University of Pakistan
13 minutes ago
nirmal ch updated their profile
1 hour ago
2 hours ago
+!!! mano stella+ liked Student's discussion past paper cs403
2 hours ago
+!!! mano stella+ liked Student's discussion CS201 Note
2 hours ago
+!!! mano stella+ liked Student's discussion Dua ki Qaboliyat
2 hours ago

1

2

3