1. Form a group of 2-3 students, and send your group details (Name in Arabic, academic No., email address) to Course Instructor before end of 5 rd week.

2. Read and understand the computational problem stated below.

3. Design a brute-force algorithm based on the given description to solve the stated problem and write its pseudocode. [2 marks]

4. Analyze the brute-force algorithm complexity and provide an asymptotic upper bound using Big-Oh notation. [2 marks]

5. Suggest a new algorithm to solve the problem with a better asymptotic upper bound. Write its pseudocode and provide its complexity using Big-Oh notation. [2 marks]

6. Implement your algorithm using Java or python. [2 marks]

7. Compile a report as PDF file (pseudocodes, running time and asymptotic upper bound analysis). [2 marks]

8. Submit your report (as PDF file) along with your .java or python file via Blackboard before the deadline.

The Computational Problem:

Assume you have two sequences and of the same length > 1, where each sequence contains integer values. The goal of this problem is to find a subsequence which has the following properties:

1. The subsequence is common to both and .

2. The subsequence length is maximum among any other common subsequences.

3. The subsequence cannot be empty.

4. The values in subsequence S are consecutive values in X and Y.

Brute-force algorithm:

Generate all possible subsequences of X, and all subsequences of Y. Then, for each subsequence sx in X, and for each subsequence sy in Y, check if sx and sy are equal. If so, then compare its length with the maximum common subsequence found so far and keep the maximum length subsequence.

--------------------------------------------------

: Input Format

Input consists of two 1-dimenional arrays of size , where > 1

Output Format

Output is:

: length of the subsequence S

: starting index in sequence X for the first element in S

: starting index in sequence Y for the first element in S

Example 1:

X={2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

Y={13, 15, 18, 1, 3, 5, 8, 10, 12, 20}

Longest common subsequence is S={8, 10, 12} with length 3.

n = 3 i = 4 j = 7