Answer Happy

Problems 1. [10 marks] Alex loves skiing and, in order to keep gaining speed, they prefer to always ski downwards. Alex collected the measured altitude of an area that they plan to go next month, represented using an array of size n by n. An example with n= 4 is given below. [4 12 15 201 6 28 23 11 9 33 50 43 18 22 47 10 Alex can start skiing from any cell and move to an adjacent cell on the right, left, up or down (no diagonals), anytime as needed. They will always ski towards an adjacent cell with a strictly lower altitude. In the above example, one possible skiing path is 50-23-15-12-4. Of course, 50-33-28-23-15-12-4 is another one, and in fact the longest possible one. (a) Write a function LongestSkiingPath(M0.n-1)0.n-1) in pseudocode, which takes a 2-D array representing for the measured altitude of an area as input and calculates the number of cells involved in the longest path, using Dynamic Programming. Using the above example, your algorithm should return 7. (b) What's the time complexity of your algorithm? Briefly justify your answer. Note: Partial marks will be awarded to working but less efficient implementations.