NEW
Font size
S
M
L
XL
WorksheetsDSBS-AN-31.01.2024
Total questions: 15
Worksheet time: 30mins
Name
Class
Date
1.
Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.
a)
33
b)
23
c)
43
d)
34
2.
Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is
a)
1500
b)
2000
c)
200
d)
100
3.
What happens when a top-down approach of dynamic programming is applied to any problem?
a)
It increases both, the time complexity and the space complexity
b)
It increases the space complexity and decreases the time complexity.
c)
It increases the time complexity and decreases the space complexity
d)
It decreases both, the time complexity and the space complexity
4.
The Fibonacci sequence is often used to illustrate dynamic programming concepts. What is the time complexity of a naive recursive implementation of Fibonacci numbers?
a)
O(1)
b)
O(log n)
c)
O(n)
d)
O(2^n)
5.
time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4 For the optimal solution which should be the starting assembly line?
a)
Line 1
b)
Line 2
c)
All of the mentioned
d)
None of the mentioned
6.
Consider the following array:
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
a)
1
b)
2
c)
3
d)
4
7.
Find the longest increasing subsequence for the given sequence:
{10, -10, 12, 9, 10, 15, 13, 14}
a)
{10, 12, 15}
b)
{10, 12, 13, 14}
c)
{-10, 12, 13, 14}
d)
{-10, 9, 10, 13, 14}
8.
Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a)
5
b)
4
c)
3
d)
6
9.
The number of increasing subsequences with the longest length for the given sequence are:
{10, 9, 8, 7, 6, 5}
a)
3
b)
4
c)
5
d)
6
10.
Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
a)
14
b)
10
c)
6
d)
100
11.
#include<stdio.h>
int fibo(int n)
{
if(n<=1)
return n;
return fibo(n-1) + fibo(n-2);
}
int main()
{
int r = fibo(50000);
printf("%d",r);
return 0;
}
a)
1253556389
b)
5635632456
c)
Garbage value
d)
Runtime error
12.
int fibo(int n)
if n == 0
return 0
else
prevFib = 0
curFib = 1
for i : 1 to n-1
nextFib = prevFib + curFib
prevFib = curFib
curFib = nextFib
return curFib
a)
O(1)
b)
O(n)
c)
O(n2)
d)
Exponential
13.
#include<stdio.h>
int fibo(int n)
{
if(n==0)
return 0;
int i;
int prevFib=0,curFib=1;
for(i=1;i<=n-1;i++)
{
int nextFib = prevFib + curFib;
prevFib = curFib;
curFib = nextFib;
}
return curFib;
}
int main()
{
int r = fibo(10);
printf("%d",r);
return 0;
}
a)
34
b)
55
c)
Compile error
d)
Runtime error
14.
Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?
a)
20
b)
12
c)
6
d)
5
15.
Fill in the blank to complete the code. #include<stdio.h>
int main()
{
int coins[10]={1,3,4},lookup[100000];
int i,j,tmp,num_coins = 3,sum=100;
lookup[0]=0;
for(i = 1; i <= sum; i++)
{
int min_coins = i;
for(j = 0;j < num_coins; j++)
{
tmp = i - coins[j];
if(tmp < 0)
continue;
if(lookup[tmp] < min_coins)
______________;
}
lookup[i] = min_coins + 1;
}
printf("%d",lookup[sum]);
return 0;
}
a)
lookup[tmp] = min_coins
b)
break
c)
min_coins = lookup[tmp]
d)
continue
Reset
