Part 1.
Develop an O(n2)-time dynamic programming algorithm to compute the Longest Monotonically Increasing Subsequence (LMIS)of a given sequence of n numbers. For example, given a sequence of 10 numbers<1 20 3 19 4 18 5 17 6 7>, the LMIS of this sequence is 1 3 4 5 6 7.
You must complete the following steps and submit your work for each step:
1) Prove that the problem to compute the LMIS exhibits optimal substructure.
2) Derive a recursive solution to the problem
3) Write the pseudo code to compute the LMIS
4) Implement your algorithm to compute the LMIS using Python, or Java (NetBeans IDE 8.0 or above), or C# (Visual Studio 2015)
5) Run your program with the three sample input files: "input1.txt", "input2.txt", and "input3.txt" attached on CougarView. If you run your program in a command line, you should be able to type the input file name. If you used a GUI for user interaction, you need to have a File Chooser button to select the input files.
6) Save the screenshots for each input file of the sample run in Word documents
7) Put everything listed above in a ZIP file including the screenshots for your sample runs.
Part 2.
Give an O(n lg n)-time algorithm to computethe LMISof a sequence of n numbers. (Hint: Observe that the last element of acandidate subsequence of length i is at least as large as the last element of a candidate subsequence of length i-1. Maintain candidate subsequences by linkingthem through the input sequence.)
You ONLY need to complete the followingsteps. Put all your work for this part in a Word document.
1) Derive a recursive solution to the problem
2) Write the pseudo code to compute the LMIS
3) Prove that your algorithm runs in O(n lg n)-time