Derive a recursive solution to the problem

Assignment Help Programming Languages

Reference no: EM131477371

Part 1.

Develop an O(n²)-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

Reference no: EM131477371

Questions Cloud

Prepare transactions and resultants report reflecting method : MPA 701 - Accounting Assessment Task - The Essay. Prepare transactions and resultants reports reflecting methods used by economic entities

Justify your investment decisions based on a trend analysis : You are required to research the foreign currencies and select two foreign currencies to invest in for the account of one of your clients who has given you $20.

Calculate the firms cash conversion cycle : Calculate the firm's cash conversion cycle given annual sales are $660,000 and cost of goods represent 80% of sales. Assume a 365-day year.

Students and faculties in college and to education : Discuss the Cold War in relation to students and faculties in college and to education.

Derive a recursive solution to the problem : CPSC 6109: Advanced Algorithms Prove that the problem to compute the LMIS exhibits optimal substructure.and Derive a recursive solution to the problem

Expansion of slavery into new territories : What compromises attempted to resolve the conflicts over the expansion of slavery into new territories?

Identity formation and cosmopolitanism : What do you think identity formation and cosmopolitanism have to do with "from such gendered shame [...] mass murderers are made"? no plagiarism

Plans are heard and accepted by management : What suggestions can you offer to ensure that risks and their plans are "heard" and accepted by management?

Rebuilding of western europe economy : How did the Marshall Plan contribute to the rebuilding of Western Europe's economy and how did this rebuilding help bring the spread of Communism.

User Account

All Pages