# The Longest Increasing Subsequence Problem

Subject Computer Science Data Structures and Algorithms

## Question

Introduction
In this project you will design, implement, and analyze two algorithms for the same problem. For this problem, you will design two separate algorithms, describe the algorithms using clear pseudocode, analyze them mathematically, implement your algorithms in C/C++/Java, measure their performance in running time, compare your experimental results with the efficiency class of your algorithms, and draw conclusions. The first algorithm has a tractable (polynomial) running time, while the second algorithm has an intractable (exponential or factorial) running time.
At the end of this document I have provided you with sample high resolution timing code in C++11, called βTemplate for a C/C++ program with high resolution timingβ. If you choose to use Java, you are responsible for figuring out how to do high resolution timing in that language.
Longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

The hypotheses
This experiment will test the following hypotheses:
1. Exhaustive search algorithms are feasible to implement, and produce correct outputs.
2. Algorithms with exponential or factorial running times are extremely slow, probably too slow to be of practical use.

The problem
The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

The longest increasing subsequence problem can be formulated as follows:
input: n, a positive integer, and the array A of n comparable elements
output: array R that contains the longest increasing subsequence
The longest increasing subsequence problem is solvable in π(_πl_o_g_π)_ _time, where π _denotes the length of the input sequence.1
1 Schensted, C. (1961), "Longest increasing and decreasing subsequences", Canadian Journal of Mathematics 13: 179β191, doi:10.4153/CJM-1961-015-3

A simple algorithm
There is a straightforward algorithm that solves the problem and has π(_π2_)_ _running time, where π _denotes the length of the input sequence. The algorithm uses an additional array H of length n, of non-negative integers. The value π»[_π]_ _will indicate how many elements, greater than π΄[_π]_ _are further in the sequence A.
Initially, the array H is set to 0 (all the elements are 0). The algorithm proceeds by trying to modify the values of π» _starting with the previous to last element and going down to the first element. Then a longest subsequence can be identified by selecting elements of A in decreasing order of the H values, starting with the largest value in H.

Algorithm End_to_Beginning
Step 1. Set all the values in the array H to 0.
Step 2. Starting with π»[_πβ1_]_ _and going down to π»[_0_]_ _try to increase the value of π»[_π]_ _as follows:
Step 3. Starting with index π+_1_ _and going up to πβ1_ _(the last index in the array A) repeat Steps 4 and 5:
Step 4. See if any element is bigger of π΄[_π]_ _and has its H value also bigger or equal to π»[_π]_.
Step 5. If yes, then π΄[_π]_ _can be followed by that element in an increasing subsequence, thus set π»[_π]_ _to be 1 plus that H value.
Step 6. Calculate the largest (maximum) value in array H. By adding 1 to that value we have the length of a longest increasing subsequence.
Step 7. Identify a longest subsequence by identifying elements in array A that have decreasing H values, starting with the largest (maximum) value in array H.

Please see the Class Notes posted on TITANium for two executions of this algorithm on two separate instances.
An exhaustive algorithm
There is an exhaustive algorithm that solves the problem and has π(_π!_)_ _running time, where π _denotes the length of the input sequence. The algorithm generates all possible subsequences of the array π΄ _and then tests each subsequence on whether it is in increasing order. The longest such subsequence is a solution to the problem.
We note that a subsequence can be uniquely identified by the set of indices in the array π΄ _that are part of the subsequence. For example, given the array
A = [1, 0, 2, 1, 5, 3, 13, 8, 34, 21, 89, 55, 233, 143]
the subsequence R = [1, 0, 3] is uniquely identified by the set of indices {0,1,5} of the elements in the array A.
To generate all possible subsequences, one may consider generating the power set of {_0_,_1_,_β―,_πβ1_}_ _and consider each subset of the power set as the set of indices in A of the subsequence.

There are several ways to generate the power set. One way is to implement an iterative algorithm that uses a stack to grow and shrink the set as needed. The benefit of this approach is that it prints the subsets in lexicographic order. Below find an implementation2 in C++ that generates the power set of the set {_0_,_1_,_β―,_πβ1_}_ _(where you can specify n in the program):
2 http://www.programminglogic.com/powerset-algorithm-in-c/
void Powerset (int n)
// function to generate the power set of {1, .., n} and retrieve the best set
int *stack, k;
stack = new int[n+1]; // allocate space for the set
stack[0]=0; /* 0 is not considered as part of the set */
k = 0;
while(1) {
if (stack[k] < n) {
stack[k+1] = stack[k] + 1;
k++;
}
else {
stack[k-1]++;
k--;
}
if (k==0) break;
}
delete [ ] stack; // deallocate space for the set
return;
}

What to do
1. Write clear pseudocode for each algorithm.
2. Analyze your pseudocode mathematically and prove its efficiency class using Big-Oh notation. (You need to compute the total number of steps of the algorithm.)
3. Type these notes (electronically or on paper) and submit it as a PDF report.
4. Implement your algorithms in C/C++/Java/python
5. Compile and execute the program.
6. Create a file with the output of the program for an input value and submit it together with the program. Note, the output can be redirected to a file (for easy printing). For example, the following command line will create an output file in Linux-based operating system called a1out.txt by re-directing the output from the screen (display) to the file a1out.txt:
K:\cs202> a.out > a2out.txt

Sample outputs for End_to_Beginning Algorithm:
Example #1:
K:\202> ast2a
CPSC 335-x - Programming Assignment #2
Longest increasing subsequence problem, end-to-beginning algorithm
Enter the number of elements in the sequence
5
Enter the elements in the sequence
0 8 4 12 2
Input sequence
0 8 4 12 2
The longest increasing subsequence has length
3
The longest increasing subsequence is
0 8 12
elapsed time: 0.000106 seconds
Example #2:
K:\202> ast2a
Longest increasing subsequence problem, end-to-beginning algorithm
Enter the number of elements in the sequence
16
Enter the elements in the sequence
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Input sequence
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
The longest increasing subsequence has length
6
The longest increasing subsequence is
0 4 6 9 13 15
elapsed time: 0.000119 seconds
Sample outputs for Powerset Algorithm:
Example #1:
K:\202> ast2b
CPSC 335-x - Programming Assignment #2
Longest increasing subsequence problem, powerset algorithm
Enter the number of elements in the sequence
5
Enter the elements in the sequence
0 8 4 12 2
Input sequence
0 8 4 12 2
The longest increasing subsequence has length
3
The longest increasing subsequence is
0 8 12
elapsed time: 0.000107 seconds

Example #2:
K:\202> ast2b
Longest increasing subsequence problem, powerset algorithm
Enter the number of elements in the sequence
16
Enter the elements in the sequence
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Input sequence
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
The longest increasing subsequence has length
6
The longest increasing subsequence is
0 4 6 9 13 15
elapsed time: 0.005204 seconds

Template for a C/C++ program with high resolution timing:
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <chrono>
using namespace std;
int main( ) {
// DECLARE VARIABLES
// PRINT THE HEADER OF THE PROGRAM
// Start the chronograph to time the execution of the algorithm
// Reading the input is NOT part of the algorithm so the timer starts after reading the input
auto start = chrono::high_resolution_clock::now();
// YOU NEED TO COMPLETE THIS PART OF CODE
// End the chronograph to time the execution of the algorithm
auto end = chrono::high_resolution_clock::now();
// DISPLAY THE OUTPUT
// Print the elapsed time in seconds and fractions of seconds
// Displaying the output is NOT part of the algorithm so the timer ends before displaying the output
int microseconds = chrono::duration_cast<chrono::microseconds>(end - start).count();
double seconds = microseconds / 1E6;
cout << "elapsed time: " << seconds << " seconds" << endl;
return EXIT_SUCCESS;
}

Template for a C/C++ program doing end-to-beginning algorithm
// Assignment 2: Longest increasing subsequence problem, end-to-beginning algorithm
// XX YY ( YOU NEED TO COMPLETE YOUR NAME )
// Given a sequence of elements the program finds a subsequence of it in which the subsequence's // elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.
// The program reads the number of elements in the sequence, then the elements and outputs the sorted // sequence and the running time.
// INPUT: a positive integer n and a list of n elements
// OUTPUT: a longest increasing subsequence of the initial sequence
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <chrono>
using namespace std;
void print_sequence(int, float*);
// function to print a sequence, given the number of elements and
// the actual sequence stored as an array
int main() {
int n, i, j, max, index;
float *A, *R;
int *H;
cout << endl << "CPSC 335-x - Programming Assignment #2" << endl;
cout << "Longest increasing subsequence problem, end-to-beginning algorithm" << endl;
cout << "Enter the number of elements in the sequence" << endl;
// read the number of elements
cin >> n;
// allocate space for the input sequence and array H
A = new float[n];
H = new int[n];
cout << "Enter the elements in the sequence" << endl;
for( i=0; i < n; i++)
cin >> A[i];
// print the sequence
cout << "Input sequence" << endl;
print_sequence(n,A);
// Start the chronograph to time the execution of the algorithm
auto start = chrono::high_resolution_clock::now();
// loop to populate the array H with 0 values
for(i=0; i< n; i++)
H[i] = 0;
// loop to calculate the values of array H
for ( i = n-2; i>= 0; i--) {
for ( j = i+1; j < n ; j++)
// WRITE THE CODE THAT IS AN IF CONDITION THAT DECIDES WHETHER
// TO CHANGE OR NOT THE VALUE OF H[i]
}
// calculate in max the length of the longest subsequence by adding 1
// to the maximum value in H

max = H[0];
for( i=1; i< n; i++)
if (max < H[i])
max = H[i];
max ++;
// allocate space for the subsequence R
R = new float[max];
// add elements to R by whose H's values are in decreasing order, starting
// with max-1
// store in index the H values sought
index = max - 1;
// store in j the index of the element appended to R
j = 0;
for(i=0; i< n; i++)
if (H[i] == index) {
// WRITE THE BLOCK OF STATEMENTS TO ADD A[i] TO THE R SEQUENCE BY
// STORYING IT INTO R[j], DECREMENTING index AND INCREMENTING j
}
// End the chronograph to time the loop
auto end = chrono::high_resolution_clock::now();
// write the output
cout << "The longest increasing subsequence has length " << endl;
cout << max << endl;
cout << "The longest increasing subsequence is" << endl;
print_sequence(max, R);
// print the elapsed time in seconds and fractions of seconds
int microseconds = chrono::duration_cast<chrono::microseconds>(end - start).count();
double seconds = microseconds / 1E6;
cout << "elapsed time: " << seconds << " seconds" << endl;
// de-allocate the dynamic memory space
delete [] A;
delete [] H;
delete [] R;
return EXIT_SUCCESS;
}
void print_sequence(int n, float *seq)
// function to print a sequence, given the number of elements and
// the actual sequence stored as an array
// n represents the number of elements in the sequence
// seq represents the actual sequence
// WRITE THE CODE TO PRINT THE ELEMENTS OF A SEQUNCE seq WITH n ELEMENTS

Template for a C/C++ program doing power set algorithm
// Assignment 2: Longest increasing subsequence problem, power set algorithm
// XX YY ( YOU NEED TO COMPLETE YOUR NAME )
// Given a sequence of elements the program finds a subsequence of it in which the subsequence's // elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.
// The program reads the number of elements in the sequence, then the elements and outputs the sorted // sequence and the running time.
// INPUT: a positive integer n and a list of n elements
// OUTPUT: a longest increasing subsequence of the initial sequence
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <chrono>
using namespace std;
void print_sequence(int, float*);
// function to print a sequence, given the number of elements the actual sequence stored as an array
void printPowerset(int, int*, int&, float*);
// function to generate the power set of {1, 2, β¦first argument} and retrieve the best set
void checkSet(int[], int, int*, int&, float*);
// function to check the currentgly generated set stack of size k the current best set bestSet of size bestSize
int main() {
int n, bestSize, i;
float *A, *R;
int *bestSet;
cout << endl << "CPSC 335-x - Programming Assignment #2" << endl;
cout << "Longest increasing subsequence problem, powerset algorithm" << endl;
cout << "Enter the number of elements in the sequence" << endl;
// read the number of elements
cin >> n;
// allocate space for the input sequence and array R
A = new float[n];
R = new float[n];
cout << "Enter the elements in the sequence" << endl;
for( i=0; i < n; i++)
cin >> A[i];
// print the sequence
cout << "Input sequence" << endl;
print_sequence(n,A);
// Start the chronograph to time the execution of the algorithm
auto start = chrono::high_resolution_clock::now();
// allocate space for the best set; initial its size is 0
bestSet = new int[n+1];
bestSize = 0;
// retrieve the indices for generating the subsequence
for(i=0;i<bestSize;i++)
// decrease each index by one since the indices of array A are in
// the range 0..n-1 and not 1..n
R[i]=A[bestSet[i+1]-1];

// End the chronograph to time the loop
auto end = chrono::high_resolution_clock::now();
// display the output
cout << "The longest increasing subsequence has length " << endl;
cout << bestSize << endl;
cout << "The longest increasing subsequence is" << endl;
print_sequence(bestSize, R);
// print the elapsed time in seconds and fractions of seconds
int microseconds = chrono::duration_cast<chrono::microseconds>(end - start).count();
double seconds = microseconds / 1E6;
cout << "elapsed time: " << seconds << " seconds" << endl;
// de-allocate the dynamic memory space
delete []A;
delete []R;
return EXIT_SUCCESS;
}

void print_sequence(int n, float *seq)
// function to print a sequence, given the number of elements the actual sequence stored as an array
// n represents the number of elements in the sequence
// seq represents the actual sequence
// WRITE THE CODE TO PRINT THE ELEMENTS OF A SEQUNCE seq WITH n ELEMENTS
void printPowerset (int n, int *bestSet, int &bestSize, float *A)
// function to generate the power set of {1, .., n} and retrieve the best set
// n represents the maximum value in the set
// bestSet represents the set
// bestSize is the size of the bestSet
int *stack,k;
// allocate space for the set
stack = new int[n+1];
stack[0]=0; /* 0 is not considered as part of the set */
k = 0;
while(1){
if (stack[k]<n){
stack[k+1] = stack[k] + 1;
k++;
}
else{
stack[k-1]++;
k--;
}
if (k==0)
break;
checkSet(stack, k, bestSet, bestSize, A);
}
// deallocate space for the set
delete [ ] stack;
return;
}

void checkSet(int *stack, int k, int *bestSet, int &bestSize, float *A)
// function to check the currently generated set stack of size k against the current
// best set bestSet of size bestSize
{
int i;

// check that the indices in stack generate a subsequence of increasing order
if (k <= 2) {
// the set contains a single index so the subsequence is in increasing order
if (k > bestSize) {
// we found a better set
// WRITE CODE TO STORE stack into bestSet and UPDATE bestSize TO k
return;
}
}
else {
// the set contains more than a single index so check that the subsequence is in order
for(i=0;i<k-1;i++) {
// decrease each index by one since the indices of array A are in
// the range 0..n-1 and not 1..n
// WRITE CODE (AN IF STATEMENT) TO CHECK THAT THE ELEMNTS IN ARRAY A
// AT INDICES stack[i+1]-1 AND stack[i+2]-1 ARE IN INCREASING ORDER
// IF THE TWO ELEMENTS ARE OUT OF ORDER THEN return
}
}
// we have an increasing so we compare it against the current best set
if (k > bestSize) {
// we found a better set
// WRITE CODE TO STORE stack into bestSet and UPDATE bestSize TO k
return;
}
else
return;
}

## 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.

1. Pseudo code for End_to_Beginning:
Input n ; takes 1 operation
Input A(n) ; takes 1 operation
Create H(n) ; takes 1 operation
Set H(n) to 0; takes n operations
For i =n-2 downto 0
For j = i+1 to n-1
If (A(i) < A(j)) and (H(i) <= H(j))
H(i) = H(j) + 1
; These loops will have 1 comparison for I = n-2, then 2 comparisons for I = n -3,
; then 3 comparisons for n-4 β¦
; this pattern is an arithmetic progression of comparisons with first element 1, step 1
;and n-1 elements. The sum for the arithmetic progression is (n β 1)*(n-2)/2
;or developed n^2/2 β 3n/2 + 1
Set max to 0; takes 1 operation
For i = 0 to n-1
If (max < H(i))
max = H(i)
; takes n operations...

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

## Related Homework Solutions

Programming Problems in C++
\$10.00
Programming
Computer Science
C++
Classes
Libraries
Command Line Arguments
Music Files
Statements
Variables
Scripts
Input
Output
Information
Underscores
Spaces
Track Numbers
Lexicographic Sorting
Songs
Nondeterministic Algorithm for K-Clique Problem
\$10.00
NP
Nondeterministic
Deterministic
Algorithm
K-Clique
Polynomial
Time
NP-Hard
NP-Complete
P
Computer Science
Data Structures
Arrays, Linked Lists, Queue and Stack Data Structures in C++
\$40.00
Algorithm
Array
List
Queue
Stack
Data
Structure
C++
Singly
Doubly
Prototype
Template
Function
Computer
Science
MergeSort Algorithm Applied to the E, X, A, M, P, L, E List
\$5.00
Computer Science
Data Structures
Merge-sort
Mergesort
Algorithm
Pseudo
Code
Alphabetical
Order
List
Merge Sort Implementation Without Recursion in C++
\$25.00
Mergesort
Merge Sort
Recursion
Merge
Sequence
Procedure
Non-Recursive
Iterative
Computer Science
Data Structures
Algorithms
Fibonacci Dynamic Programming Questions
\$8.00
Fibonacci
Dynamic
Programming
Question
Pseudo
Code
Algorithm
DP
Optimal
Subproblem
Live Chats