Please help with excerise with 10.8 Exercise 10.8. Consider a highway that is M

Question

Please help with excerise with 10.8

Exercise 10.8. Consider a highway that is M miles long consisting of L lanes. At every mile, there exists a lane that is blocked from mile i to (just before) milei +1. This information is recorded in an array LC[0, 1,... , M 1] oflength M, where LC(i) -j means lane j is blocked from milei toi+1 For example, LC = [1,1. 3.4.1.2.2.5.4.2.2) describes the blockages on a 5-line highway of length 11. The objective is to find a route making the minimum number of lane changes. Changing from one lane into another one has a cost of 1. For the example given above, a solution with one lane change exists: start in lane 5 and change into lane 1 at mile 6 or later. It is not hard to see that more than one optimal solution can exist. (i) For M -12 and L - 4 give an example of blocked positions that maximizes the number of lane changes. State the bound in terms of M and L and explain vour answer (ii) Consider now a greedy algorithm that starts in the lane having the farthest occurrence of a blockage and, whenever forced to switch lanes, it always switches into the lane having the farthest occurrence of a blockage. In the above example, greedy will start in lane 5 (since lane 5 has the farthest occurrence of the blockage) and at mile 6 change into lane 1 or lane 3 (these two lanes have no further blockages). Describe this greedy approach in pseudo-code and analyze its time performance in terms of M and L. Do not assume that either of these variables is a constant. Make sure to describe what data structures are used to select the next lane after a lane change. (iii) Prove that this greedy approach always generates a solution mini- mizing the number of lane changes

Explanation / Answer

i)for the above we can said for 11miles 5 lanes having the Lc(1,1,3,4,1,2,2,5,4,2,2) like for 12 miles with 4 lanes Lc is (1,3,5,2,3,6,4,3,4,5)

iii)

Greedy algorithm is used to find the minimal distance or minimal changes.And this gives the minimizing yhe number of changes by the above output.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.