Ouestion 1

1.1 [15 points] Design an algorithm with O(n2)-time complexity to find the longest monotonically increasing subsequence of n numbers For example: If the given list is 11, 5, 5, 11, 23, -20, -30, 99, 0, 22, the longest monotonically increasing subsequence is f1, 5, 5, 11, 23, 991 Write your pseudocode in the following format. Explain why yor algorithm is O(n2) - e.g. Which line takes O(n) and which other line takes O(n) Algorithm Longest-Mono-Increasing-SubseQ-VER1 Input Output Line 1: Line 2: Line 3: Line 4: 1.2 [10 points] Implement your algorithm in a programming language of your choice 1.3 [5 points] Randomly generate 100 lists of 10 elements, prepare to compare with the algorithm in Question 2 1.4 [5 points] Show 5 randomly generated lists of 10 elements and the result returned by your algorithm 1.5 [5 points] Randomly generate 100 lists of 100 elements, prepare to compare with the algorithm in question 2 1.6 [5 points] Randomly generate 100 lists of 104 elements, prepare to compare with the algorithm in question 2 1.7 [5 points] Randomly generate 100 lists of 10s elements, prepare to compare with the algorithm in question 2. If your computer runs out of memory, please state SO