4. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest...

 

Transcribed Image Text:

4. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm outputs two integers: the initial and final indices of the longest subarray. (a) (4 marks) Give the algorithm pseudocode. (b) (1 mark) Justify your big-Oh (1 mark). A solution that uses extra memory that is in O(1) is worth 100%; if you use O(n) extra memory your solutions is worth 80%. Example: If n = 10 and A= [8,6,7,10,-2,4,5,6,2,5] then the algorithm outputs 4 and 7, since A[4..7] [-2, 4, 5, 6] is the longest sorted subarray. 4. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm outputs two integers: the initial and final indices of the longest subarray. (a) (4 marks) Give the algorithm pseudocode. (b) (1 mark) Justify your big-Oh (1 mark). A solution that uses extra memory that is in O(1) is worth 100%; if you use O(n) extra memory your solutions is worth 80%. Example: If n = 10 and A= [8,6,7,10,-2,4,5,6,2,5] then the algorithm outputs 4 and 7, since A[4..7] [-2, 4, 5, 6] is the longest sorted subarray.

Answer rating: 100% (QA)

a PSEUDO CODE longestsortedsubarray size Declare MAX1 len1 i1 j0 initialpos0 finalpos1 ifarrayiarray... View the full answer