Question

2. Suppose you and your friend live on the same street D miles away from each other. Between your house and your friend's house there are n motorized scooters positioned at distances x1,22,...,-n miles from your house towards your friend's house. Each scooter has a battery that may or may not be fully charged. Let's say that the scooters can take you distances di, d2,.... dn miles down the road and you have access to all of this information before you go. Any time you encounter another scooter, you may take the new scooter and leave your old scooter behind There is an additional scooter at your house that you start with and it can go distance do miles. You wish to go to your friend's house minimizing the number of times you change scooters. Your House Your Friend's 田 田 X4 X5 5 points Describe a graph whose paths represent sequences of scooters you could use 10 points Design an algorithm that solves this problem efficiently using this graph. (6 points for correct algorithm and correctness proof and 4 points for time analysis.)

We are given n,x1,x2,...,xn,d1,d2,...,dn,D. The graph is not given and it should be constructed. The time it takes to construct a graph is part of the overall time complexity, so it should be included.

The solution is your algorithm, which includes the graph construction. It is fine if the algorithm consists of several parts, which perform different tasks. The algorithm should return the actual path.The proof and run-time analysis should be provided for the entire solution/algorithm.

Please show your wrok. Tyvm!

Answer 1

2.

Xn-1 s1 x1 d1 s2 x2 d2 s3 sn xn x3 d3 dn

Algorithm:

Input: Let say we have the scooters s0,s1,s2,... ... , sn at distances x0, x1, x2, ... ..., xn respectively.

And the scooters can travel distances d0, d1, d2, ... ..., dn respectively.

1. dist $\leftarrow$ d0

2. if(dist > (x₁ - x₀) )

3. then {

4. take s1.

5. j $\leftarrow$ 1

6. dist $\leftarrow$ dist - (x₁ - x₀)

7. i $\leftarrow$ 1

8. while(i <= n)

9. {

10. if( dist > (x_i+1 - x_i) )

11. continue with scooter s_j.

12. else

13. { dist = di.

14. if(dist > (x_i+1 - x_i) )

15. { j++.

16. take s_j.

17. dist = dist - (x_i+1 - x_i)

18. }

19. else

20. return.

21. }

22. i++

23. }

24. }

25. else

26. return.

Here at each scooter, we compare the next distance with the distance can be traveled with the battery left in the running scooter. if it can travel up to the next scooter then only we continue with it or we take the new scooter. So here we change our scooter only when the current scooter can't travel the next distance.

We are minimizing the changing of scooter efficiently such that if possible the scooter s0 can travel up to the destination.

if d0 >= D.

Time complexity: At each point, we take constant time to decide whether to take a new scooter or not. And we check the same for n points. So the time complexity will be O(n).