4. (2 points) There is an n x n grid of one-way street network. At any intersection, you may either travel from west to east or north to south. You want to compute the number of different ways in which you can travel from the north-west corner to the south-east corner. We will develop a dynamic programming solution for this problem. (Below is an erample of a 6 x 6 (i.e., n = 6). We are interested in finding the number of different ways of going from the top-left corner to the bottom-right corner.) Let W(i, j) denote the number of different ways of going from top-left corner to bottom-right corner for a grid of size i xj i.e., the grid has i horizontal lines and j vertical lines). (a) What is the value of W(1,j) for any j and W(,1) for any i? (b) Write Wij) in terms of Wi-1, j) and Wi, j - 1) when i, j> 1. Give brief explanation for the relationship that your give. (c) Use the recursive formulation developed in (b) to design an algorithm that outputs the number of different ways of going from top-left corner to bottom-right corner of an nx n grid. Give pseudocode for your algorithm. (d) Discuss running time of your algorithm. 4. (2 points) There is an n x n grid of one-way street network. At any intersection, you may either travel from west to east or north to south. You want to compute the number of different ways in which you can travel from the north-west corner to the south-east corner. We will develop a dynamic programming solution for this problem. (Below is an erample of a 6 x 6 (i.e., n = 6). We are interested in finding the number of different ways of going from the top-left corner to the bottom-right corner.) Let W(i, j) denote the number of different ways of going from top-left corner to bottom-right corner for a grid of size i xj i.e., the grid has i horizontal lines and j vertical lines). (a) What is the value of W(1,j) for any j and W(,1) for any i? (b) Write Wij) in terms of Wi-1, j) and Wi, j - 1) when i, j> 1. Give brief explanation for the relationship that your give. (c) Use the recursive formulation developed in (b) to design an algorithm that outputs the number of different ways of going from top-left corner to bottom-right corner of an nx n grid. Give pseudocode for your algorithm. (d) Discuss running time of your algorithm