Shortest-path counting 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 form one corner 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.
a) Formulate a dynamic programming algorithm for solving the above problem. Provide a description in words and pseudocode.
b) State and prove the time and space efficiencies of your algorithm in terms of order notation (e. g., Big-Oh).
c) Solve the problem using elementary combinatorics.