Dynamic Programming You are part of a team building a west-east highway that runs through an ecological preserve that cannot be avoided. You want to build the highway so it disturbs the least number of endangered species. Ecologists have mapped the territory and determined the number of endangered species for every cell in a grid that is n columns east-to-west and m rows north-to-south. Your job is to determine a path for the highway that disturbs the minimum number of species. The highway can begin in any of the m rows on the west side of the preserve and can end in any of the m rows on the east side of the preserve. The highway must always move east but at each step it can move to the cell immediately east, the cell to the north-east, or the cell to the south-east. On the next page is an example preserve with west on the left and east on the right. This example has 8 columns and 8 rows. The number in each cell is the number of endangered species that live in that cell. a) Let Mi, j) express the minimum number of species that will be disturbed by a highway that ends in cell (i, j). Show a self-reduction from this problem to its sub-problems.
b) State a dynamic programming algorithm in pseudocode that solves this problem using the self-reduction from above. You do not need to give code for recovering the solution.
c) What is the worst case runtime of your algorithm?
d) Use your algorithm to find the minimum cost highway of the example input. 7 0 4 7 3 2 14 5 4 14 5 3 6 6 4 6 12 2 2 5 7 4 6 5 25 25 9 21 8 8 8 6 23 3 12 2 12 5 3 5 4 3 1 4 2 15 7 12 3 4 2 9 3 4 3 7 5 2 4 7 12 18 1 10 Fill in this grid using your algorithm and then indicate the minimum cost highway.