## Question

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 Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse 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...

This is only a preview of the solution. Please use the purchase button to see the entire solution