b. Let M(i, j) denote the maximum number of pebbles that can be collected when moving from cell-(1, 1) to cell-(i, j). Derive a recurrence relation for M(i, j).

c Using the recurrence in 1(b), give pseudocode for a recursive algorithm to compute M(i, j).

d. Give pseudocode for an efficient dynamic programming scheme to compute M(i, j). Analyze the space and time complexity of your algorithm.

e. Give pseudocode for an algorithm that prints the path from cell-(1, 1) to cell-(i, j) which leads to the collection of maximum number of pebbles. Analyze the space and time complexity of your algorithm.

1. Consider a table composed of mxn cells, where m, n > 0. Each cell of the table has a certain number of pebbles and a cell at ith row and j'h column of the table is referred to as cell-(ij). Such a table can be represented as a 2D array A[1...m, 1...n], where A[i, j] denotes the number of pebbles in cell-ci, j) and A[i, j]>0 for all i, j. You start from cell-(1, 1) and move towards the cell-(m, n) with a constraint that in each step you either go down or go right by one cell i.e. from cell-i, j) you either go to cell-(i+1, j) or cell-(i, j+1). Your goal is to move from cell-(1, 1) to cell-(m, n) collecting the maximum number of pebbles. For example, consider the table below with 4 x 5 cells 1 2 3 4 5 18 117 93 2 2213 5 8 11 39 15 23 47 4 11 1 4 25 17 The maximum number of pebbles collected when you move from cell-(1, 1) to cell-(4, 5) is 127 and the path that leads to it is given by: (1, 1) (2, 1) (2, 2) (3, 2) (3, 3) (4, 3) (4,4) (4, 5) 8 117 93 22 13 5 8 11 9 15 23 4 7 11 14 25 17 (a.) What is the length of any path from cell-(1, 1) to cell-(m, n)? 5 pts 1. Consider a table composed of mxn cells, where m, n > 0. Each cell of the table has a certain number of pebbles and a cell at ith row and j'h column of the table is referred to as cell-(ij). Such a table can be represented as a 2D array A[1...m, 1...n], where A[i, j] denotes the number of pebbles in cell-ci, j) and A[i, j]>0 for all i, j. You start from cell-(1, 1) and move towards the cell-(m, n) with a constraint that in each step you either go down or go right by one cell i.e. from cell-i, j) you either go to cell-(i+1, j) or cell-(i, j+1). Your goal is to move from cell-(1, 1) to cell-(m, n) collecting the maximum number of pebbles. For example, consider the table below with 4 x 5 cells 1 2 3 4 5 18 117 93 2 2213 5 8 11 39 15 23 47 4 11 1 4 25 17 The maximum number of pebbles collected when you move from cell-(1, 1) to cell-(4, 5) is 127 and the path that leads to it is given by: (1, 1) (2, 1) (2, 2) (3, 2) (3, 3) (4, 3) (4,4) (4, 5) 8 117 93 22 13 5 8 11 9 15 23 4 7 11 14 25 17 (a.) What is the length of any path from cell-(1, 1) to cell-(m, n)? 5 pts