Homework 3 Solution

Traffic lane problem Consider a roadway with three traffic lanes, each consisting of cells as shown in the figure below.























































The lanes are denoted by columns c1, c2 and c3. Each lane is marked with levels l1, l2, ..., ln, so the cells are denoted by pairs of lanes and levels. For instance, (l1; c2) denotes the cell at level 1 of the traffic lane 2. The roadway has some obstacles; the cells covered by these obstacles are colored as red in the figure.




Initially, there is a car at cell (0; 1) of this roadway. The car can move forward with the goal of reaching a cell at level ln, obeying the following rules:




Rule 1 The car can not move through the cells covered by obstacles.




Rule 2 The car has to move forward to a neighboring cell at the next level. For instance, if the car is located at a cell (li; c0) then it has to move straight to (li+1; c0) or diagonally to (li+1; c1).




Therefore, the car cannot move between the cells at the same level, and it cannot go back to a cell at the previous level.




Rule 3 The car cannot jump over cells. Therefore, it cannot go from c0 to c2 or from c2 to c0 in one step. It cannot jump from level li to lj where j i + 1 or j < i 1.




Note that, according to these rules, the car can move to one of the three cells at the next level only if it is at c1.




The traffic lane problem aims to find a route for the car to reach one of the cells at the last level, so as to minimize the number of traffic lane changes.




1



CS301, Homework 3










Submit PDF Write a report including the following:




Recursive formulation of the traffic lane problem: Identify the subproblems, observe the optimal substructure property and the overlapping computations, and then define the problem recursively.



Pseudocode of a naive recursive algorithm based on your recursive formula-tion, and its complexity analysis (i.e., the asymptotic time and space complex-ity).



Pseudocode of a recursive algorithm that builds solutions to your recurrence from top down with memoization, and its complexity analysis (i.e., the asymp-totic time and space complexity).



Pseudocode of an iterative algorithm that builds solutions to your recurrence from bottom up, and its complexity analysis (i.e., the asymptotic time and space complexity).



Experimental evaluations of these three algorithms: plot the results in a graph, and discuss the results (e.g., are they expected or surprising? why?)



Submit Python Code, and Benchmarks




Implement in Python the three algorithms above, designed to solve the traffic lane problem.



The roadway will be presented as an input matrix of size n 3. The entry at the i’th row and j’th column of the matrix is 0, if the cell (li; cj ) is a free cell (i.e., not occupied by an obstacle); otherwise, it is 1.




Create a benchmark suite to test the correctness of your Python programs: take into account the functional testing methods (e.g., white box and lack box testing) while constructing the instances, and test your programs with these instances.



Create a benchmark suite to test the performance of your Python programs: construct instances of different sizes (e.g., relative to the number of levels), evaluate the performance of your programs in terms of computation times, and plot the results within a graph.



Demos Demonstrate that your Python programs correctly compute solutions for your benchmark instances, and for the instances that will be provided by us. Demo day will be announced.




2