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 west$-$to$-$east

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.

This 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$)$ State this problem with formal input and output conditions.

b$)$ Let $M(c,r)$ express the minimum number of species that will be disturbed by

a highway that ends in cell $c,r$ where $c$ and $r$ are indexes of a column or row

$($respectively$).$ Show a self$-$reduction from this problem to its sub$-$problems.

c$)$ State a dynamic programming algorithm in pseudocode that computes $M(c,r)$

using the self$-$reduction from above.

d$)$ Describe how you can recover the path the highway should take to disturb the

fewest endangered species.

e$)$ What is the worst case time and space complexity of your algorithm?

f$)$ Use your algorithm to find the minimum cost highway of the example input. Make

sure to show your matrix and highlight the path of the minimum cost highway.