Assignment for next class

[Moin Mostakim]

Dear Students,


I hope you have a lot of fun during hartal. To enhance your fun stuff there is a challenging problem which has been attached with this e-mail. You need to code and verify the correctness of greedy algorithm.

Hopefully you will bring this assignment on time. (The algorithm approach is already given.) If you found some counter example that disproves the correctness of this algorithm would receive some bonus marks.

Thanks in advance

Moin Mostakim.

[Shihab Ullah]

Sir,
I tried downloading and open it in many ways several times...I think there is some problem with the given docx file.

Moin Mostakim.

--
You received this message because you are subscribed to the Google Groups "Dashboardalgorithm" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dashboardalgori...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Zafor Iqbal]

yes sir! Seems problem with the file! Corrupted!Ms Word Can't open it!

--
Regards,

Zafor Iqbal

[Moin Mostakim]

Problem Specification:



There are n gas stations positioned along a circular road. Each has a
limited supply of gas. You can only drive clockwise around the road.
You start with zero gas. Knowing how much gas you need to get from
each gas station to the next and how much gas you can get at each
station, design an algorithm to find the gas station you need to start
at to get all the way around the circle.



A proposed algorithm:



Here's an approach that works in O(n) time and O(1) space



Start at any station, call it station 0, and advance until you run out
of gas. If you don't run out of gas, done. Otherwise, if you run out
between stations k and k+1, start over again at station k+1. Make a
note if you pass 0 again, and if you run out after that it can't be
done.

The reason this works is because if you start at station i and run out
of gas between stations k and k+1, then you will also run out of gas
before station k+1 if you start at any station between i and k.





You have to implement the above approach By Java Programming . You
will have to explain why your answer will be correct. That means you
have to show this algorithm is correct or not.



If not please show an counter example.



You have to submit it on next Schedule that means the first class of
the Lab we are going to have may be (Saturday or Sunday).

[Md. Shazzed Hosen]

Try wordpad to open that file.