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)