Please help with excersise 10.8 section (ii) and (iii)
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 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
