Write the algorithm in a format like this :

//Applies dynamic programming to compute the largest number of

//coins a robot can collect on an n m board by starting at (1, 1)

//and moving right and down from upper left to down right corner

//Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and 0

//for cells with and without a coin, respectively

//Output: Largest number of coins the robot can bring to cell (n, m)

F[1, 1]? C[1, 1]; for j ? 2 to m do F[1, j ]? F[1, j ? 1] + C[1, j ]

for i ? 2 to n do

F[i, 1]? F[i ? 1, 1] + C[i, 1]

for j ? 2 to m do

F[i, j ]? max(F[i ? 1, j ], F[i, j ? 1]) + C[i, j ]

return F[n, m]

Exercise 8.1, problem 7 (a) only A chess rook can move horizontally or vertically to any square in the same row or in the same column of a chessboard. Find the number of shortest paths by which a rook can move from one comer of a chessboard to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the first and the last squares. Solve the problem ic programming algorithm a. by a dynam Hint: a chessboard consists of 8x8 squares. You can assume that the chess rook is initially located at the top left corner. You wanted to find the number of the shortest path to move the rook from the top left corner to the bottom right corner. This problem is similar to the path counting problem from the slides. For example, there are 3 different shortest paths to move the rook from (1, 1) to (2, 3) (1, 1) to (1, 2) to (2, 2) to (2, 3) (1, 1) to (2, 1) to (2, 2) to (2, 3)