## Description

Q1. Write the code for Fibonacci sequence in the following two ways:

a) Recursive version.

b) Dynamic programming.

For each of the two sub-problems, you have to compute the execution time and return the

number of computations.

The Fibonacci series is given as:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the following

recurrence relation:

Fn = Fn-1 + Fn-2

with seed values

F0 = 0 and F1 = 1.

In your program, use large values of “n”.

Input: n = 2

Output: 1,1

Execution Time: xxx ms %%% Correct this.

Number of Computations: %%% Correct this.

Input: n = 9

Output: Write the list here.

Execution Time: yyyyy ms %%% Correct this.

Number of Computations: %%% Correct this.

Q2a.Given a sequence of matrices, write a program to find the most efficient way to multiply

matrices together. Note: You need not perform the multiplications, the goal is to merely decide

upon the order of multiplication.

Input: p[ ] = {40, 20, 30, 10, 30}

Output: 26000

There are 4 matrices of dimensions 40×20, 20×30, 30×10 and 10×30.

Let the input 4 matrices be A, B, C and D. The minimum number of multiplications are

obtained by putting parenthesis in following way

(A(BC))D –> 20*30*10 + 40*20*10 + 40*10*30

Input: p[] = {10, 20, 30, 40, 30}

Output: 30000

There are 4 matrices of dimensions 10×20, 20×30, 30×40 and 40×30. Let the input 4 matrices

be A, B, C and D. The minimum number of multiplications are obtained by putting parenthesis

in following way

((AB)C)D –> 10*20*30 + 10*30*40 + 10*40*30

Input:

The first line of each test case contains an integer N, denoting the number of elements in the

array. Then next line contains N space separated integers denoting the values of the element

in the array.

Output:

For each test case the print the minimum number of operations needed to multiply the chain

with the proper place of the parenthesis.

Example 1:

Input:

5 # no. of inputs

1 2 3 4 5 # Inputs

Output:

38 1(2(3(45)))

Example 2:

Input:

3 # No. of inputs

3 3 3 # inputs

Output:

27 ((12)3)

Q2b Write an ‘LCS’ function that takes two sequences and finds the length of the longest

common subsequence.

Function prototype:

“int lcs( char *X, char *Y, int m, int n )”

A subsequence is a sequence that appears in the same relative order, but not necessarily

contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ”acefg”, .. etc are subsequences of

“abcdefg”.

Example:

Input:

ABCDGH

AEDFHR

Lab Code: ECSE202L Max Marks: 10

Final Output:

3 ADH

Interpretation :

common ‘ADH’ sub-sequence is of length 3. (A, D, H)