We define the Longest MatPath as the longest path of integers in a matrix of unique...

 

Transcribed Image Text:

We define the Longest MatPath as the longest path of integers in a matrix of unique integers, such that each integer forming the path is adjacent to one another and increasing by a value of one. For example: suppose we have the following matrix: 4 5 7 8 1 2 6 9 11 3 13 12 10 14 15 16 The longest path in the above matrix is {6, 7, 8, 9]. (a) Write a recursive algorithm that, given an n x n matrix and a starting index (where 6 in the above example has index (2, 3)), returns the longest path starting at this integer. (b) Write another algorithm that runs the above algorithm as a subroutine and finds the longest path in the matrix overall. (c) Modify your origianl algorithm, so that it stores longest paths it has already calculated and uses this storage to avoid making unnecessary recursive calls. We define the Longest MatPath as the longest path of integers in a matrix of unique integers, such that each integer forming the path is adjacent to one another and increasing by a value of one. For example: suppose we have the following matrix: 4 5 7 8 1 2 6 9 11 3 13 12 10 14 15 16 The longest path in the above matrix is {6, 7, 8, 9]. (a) Write a recursive algorithm that, given an n x n matrix and a starting index (where 6 in the above example has index (2, 3)), returns the longest path starting at this integer. (b) Write another algorithm that runs the above algorithm as a subroutine and finds the longest path in the matrix overall. (c) Modify your origianl algorithm, so that it stores longest paths it has already calculated and uses this storage to avoid making unnecessary recursive calls.