Let L be an array of n distinct integers. Write and implement an efficient algorithm to find the length of a longest increasing subsequence of entries in L. For example, if the entries are 11, 17, 5, 8, 6, 4, 7, 12, 3, a longest increasing subsequence is 5, 6, 7, 12.

A- Choose an appropriate problem solving technique;

B- Select your favorite programming language such as C, C++, or Java. In that language, write, implement, and test an algorithm using the problem solving technique that you chose;

C- Analyze your implementation using either order notation analysis or empirical analysis.

Prepare a report of the following items in PDF or MS Word format:

A- Discussion of problem solving technique used and why chosen.

B- Algorithm (pseudocode, source, etc.)

C- Correctness (executables, test plans, scripts of runs, etc.)

D- Analysis (at least one order notation analysis).

The information MUST be organized in a logical and readable fashion to show the effort that you have put into researching your problems.

Executable file names must be indicated in your source code headers and directions for running your programs must be given.

In addition, you must prepare a separate page providing the instructions to compile and execute your program, such as the development environment (e.g., Visual Studio). If no such information is provided, and your program fails to build and run, points will be deducted by your professor, as appropriate.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

We use Dynamic Programming to solve the longest increasing subsequence problem. Suppose the original input sequence is S[0],S[1],…S[n-1] where n is the length of the sequence. Define an array LIS[0],LIS[1],…LIS[n-1] where LIS[i] contains the length of longest increasing subsequence starting from S[i]. To calculate LIS[i], we use dynamic programming. Suppose we already have LIS[i+1], LIS[i+2],…,LIS[n-1] , Since S[i] is the first element of the longest increasing subsequence starting from S[i], we only need to find the location of the second element. To find LIS[i], we search the right half of array S[i+1],S[i+2],..,S[n-1], for all the elements which is greater than S[i], we find the element S[k] with maximal LIS[K]. Then LIS[i]=LIS[k]+1...

By purchasing this solution you'll be able to access the following files:
Solution.cpp, Solution1.txt and Solution2.docx.

for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats