2. (Greedy - 20 points) You need to navigate a certain terrain. The view of the terrain from the top (similar to Google maps, for example) can be represented by a 2-dimensional array A of size n x 2m. You need to design a route from the cell in the first row and the first column, i.e., cell (1,1), to the cell in the last row and last column, i.e., cell (n,2"). Each cell (1.j) requires certain time (nonnegative) A[i,j] to pass through it. However, the terrain is rather regular, so that each column in A is exactly the same, i.e., A[i,j] = A[i,k] for all i, j, k. Thus, you are not given the array A explicitly because this would take exponential in n space and it would just contain lots of repetitions. Instead, you are just given the first column of the 2-d array A as a 1-d array T[1.n), i.e., T[i] = A[1,1]. Your goal is to efficiently compute the shortest time to travel from cell (1.1) to cell (n,2"). (Note that entering cell (1,1) already incurs A[1,1] time.) From each cell you can only move to a neighboring cell immediately to the North, South, West, or East of the current cell (no diagonal moves). Design a greedy algorithm for this task. Solutions with runtime 2" or more receive the grade of 0. Input: n. 71..n), where [] Zno. Output: the shortest time to navigate from cell (1,1) to cell (n, 2") in the array A formed out of T as described above. (a) (5 points) Describe your algorithm in plain English. (b) (5 points) Describe your algorithm in pseudocode. (c) (5 points) Formally prove that your algorithm is correct. (d) (5 points) State and justify the running time of your algorithm. 2. (Greedy - 20 points) You need to navigate a certain terrain. The view of the terrain from the top (similar to Google maps, for example) can be represented by a 2-dimensional array A of size n x 2m. You need to design a route from the cell in the first row and the first column, i.e., cell (1,1), to the cell in the last row and last column, i.e., cell (n,2"). Each cell (1.j) requires certain time (nonnegative) A[i,j] to pass through it. However, the terrain is rather regular, so that each column in A is exactly the same, i.e., A[i,j] = A[i,k] for all i, j, k. Thus, you are not given the array A explicitly because this would take exponential in n space and it would just contain lots of repetitions. Instead, you are just given the first column of the 2-d array A as a 1-d array T[1.n), i.e., T[i] = A[1,1]. Your goal is to efficiently compute the shortest time to travel from cell (1.1) to cell (n,2"). (Note that entering cell (1,1) already incurs A[1,1] time.) From each cell you can only move to a neighboring cell immediately to the North, South, West, or East of the current cell (no diagonal moves). Design a greedy algorithm for this task. Solutions with runtime 2" or more receive the grade of 0. Input: n. 71..n), where [] Zno. Output: the shortest time to navigate from cell (1,1) to cell (n, 2") in the array A formed out of T as described above. (a) (5 points) Describe your algorithm in plain English. (b) (5 points) Describe your algorithm in pseudocode. (c) (5 points) Formally prove that your algorithm is correct. (d) (5 points) State and justify the running time of your algorithm