Free Printable DAA 2023- 2024 Test 4

1.

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

a)

O(N)

b)

O(Sqrt(N))

c)

O(N / 2)

d)

O(log N)

2.

The complexity of Binary search algorithm is

a)

O(n)

b)

O(log n)

c)

O(n2)

d)

O(n log n)

3.

Time Complexity of this program:

def f():

a = 0

for i = 1 to n:

a += i;

b = 0

for i = 1 to m:

b += i;

a)

O(n)

b)

O(m)

c)

O(n+m)

d)

O(n*m)

4.

The complexity of Bubble sort algorithm is

a)

O(n)

b)

O(log n)

c)

O(n2)

d)

O(n log n)

5.

If for an algorithm time complexity is given by O(1) then complexityof it is:

a)

constant

b)

polynomial

c)

exponential

d)

none of the mentioned

6.

If for an algorithm time complexity is given by O(log2n) then complexity will:

a)

constant

b)

polynomial

c)

exponential

d)

none of the mentioned

7.

If for an algorithm time complexity is given by O(n) then complexityof it is:

a)

A. constant

b)

B. linear

c)

C. exponential

d)

D. none of the mentioned

8.

To measure Time complexity of an algorithm Big O notation is used which:

a)

A. describes limiting behaviour of the function

b)

B. characterises a function based on growth of function

c)

C. upper bound on growth rate of the function

d)

D. all of the mentioned

9.

What is the time complexity of following code:

int a = 0;

for (i = 0; i < N; i++) {

for (j = N; j > i; j--) {

a = a + i + j;

}

a)

O(N)

b)

O(N*log(N))

c)

O(N * Sqrt(N))

d)

O(N*N)

10.

What is the time complexity of following code:

int i, j, k = 0;

for (i = n / 2; i <= n; i++) {

for (j = 2; j <= n; j = j * 2) {

k = k + n / 2;

}

a)

O(n)

b)

O(nLogn)

c)

O(n^2)

d)

O(n^2Logn)

11.

Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?

a)

0

b)

3

c)

4

d)

None of the above

12.

Which of the following problems is NOT solved using dynamic programming?

a)

0/1 knapsack problem

b)

Matrix chain multiplication problem

c)

Edit distance problem

d)

Fractional knapsack problem

13.

In which of the following cases will the edit distance between two strings be zero?

a)

When one string is a substring of another

b)

When the lengths of the two strings are equal

c)

When the two strings are equal

d)

The edit distance can never be zero

14.

Which of the following is not the longest common subsequence between the strings "hbcfgmnapq" and

"cbhgrsfnmq"?

a)

hgmq

b)

cfnq

c)

bfmq

d)

hgmp

15.

The time complexity of Floyd's algorithm is

a)

O( $n^2$ )

b)

O( $n^3$ )

c)

O( $2^n$ )

d)

O(nlogn)

16.

Consider the given graph. Which one the following can not be the second vertex in the topological ordering?

a)

A

b)

B

c)

G

d)

D

17.

What are 2 things required in order to successfully use the dynamic programming technique?

a)

Optimal sub structure and overlapping sub problems

b)

A problem that can’t be sub divided and is complex

c)

Non overlapping sub problems and intervals

d)

Recursion and a problem that is complex

18.

Dynamic Programming is often used for (choose all that apply):

a)

Optimization problems that involve making a choice that leave one or more subproblems to be solved.

b)

Problems previously solved using divide and conquer that have over lapping subproblems

c)

Non polynomial solution problems

d)

Subproblems where resources are shared

19.

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

a)

170

b)

200

c)

160

d)

90

20.

Dynamic programming problems require making a sequence of interrelated decisions, where each decision corresponds to one stage of the problem.

a)

True

b)

False

21.

Dynamic programming problems always have a finite number of states

a)

True

b)

False

22.

The states in a dynamic program are the various possible conditions in which the system might be at that stage of the problem

a)

True

b)

False

23.

The effect of the policy decision is to transform the current state to a state associated with the beginning of the next stage

a)

True

b)

False

24.

Dynamic programming, as linear programming, can solve only deterministic problems

a)

True

b)

False

25.

In a network representation, the state variables are shown in:

a)

the links

b)

the nodes

c)

the values on the links

26.

The principle of optimality in Dynamic programming means:

a)

knowledge of past states is necessary for determining the optimal policy

b)

knowledge of the current state is sufficient for determining the optimal policy

c)

the optimal policy is independent of the states of the system

27.

What does dynamic programming do, actually?

a)

solving recurrence problems with overlapping subproblems

b)

solving recurrence problems

c)

making the solution dynamic and flexible

d)

can only finding short part in graph

28.

The efficiency of Warshall and Floyds are same

a)

true

b)

false

29.

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memoization

d)

Greedy

30.

A greedy algorithm can be used to solve all the dynamic programming problems.

a)

True

b)

False

31.

1.Which of the following is/are the property/properties of a dynamic programming problem?

a)

a)Optimal structure

b)

b)Overlapping subproblems

c)

c)Greedy algorithm

d)

d)Both optimal substructure and overlapping subproblems

32.

5.Which of the following problems should be solved using dynamic programming?

a)

a) Mergesort

b)

b) Binary search

c)

c) Longest common subsequence

d)

d) Quicksort

33.

Which of the following is/are property/properties of a dynamic programming problem?

a)

Optimal substructure

b)

Overlapping subproblems

c)

Greedy approach

d)

d) Both optimal substructure and overlapping subproblems

34.

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memoization

d)

Greedy

35.

If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memoization

d)

Greedy

36.

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

a)

Dynamic programming

b)

Greedy

c)

Divide and conquer

d)

Recursion

37.

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.

a)

True

b)

False

38.

A greedy algorithm can be used to solve all the dynamic programming problems.

a)

True

b)

False

39.

Which of the following problems is NOT solved using dynamic programming?

a)

0/1 knapsack problem

b)

Matrix chain multiplication problem

c)

Edit distance problem

d)

Fractional knapsack problem

40.

Dynamic programming divides problems into a number of

a)

conflicting objective functions.

b)

decision stages.

c)

unrelated constraints.

d)

policies.

41.

The relationship between stages of a dynamic programming problem is called a(n)

a)

state.

b)

random variable.

c)

node.

d)

Transformation.

42.

In dynamic programming, the output to stage n become the input to

a)

stage n-1.

b)

stage n itself.

c)

stage n+1.

d)

stage n-2.

43.

In dynamic programming, the technique of storing the previously calculated values is called ___________

a)

Saving value property

b)

Storing value property

c)

Memorization

d)

Mapping

44.

Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?

a)

0

b)

3

c)

4

d)

None of the above

45.

What are 2 things required in order to successfully use the dynamic programming technique?

a)

Optimal sub structure and overlapping sub problems

b)

A problem that can’t be sub divided and is complex

c)

Non overlapping sub problems and intervals

d)

Recursion and a problem that is complex

46.

Dynamic Programming is often used for (choose all that apply):

a)

Optimization problems that involve making a choice that leave one or more subproblems to be solved.

b)

Problems previously solved using divide and conquer that have over lapping subproblems

c)

Non polynomial solution problems

d)

Subproblems where resources are shared

47.

The difference between Divide and Conquer and Dynamic Programming is:

a)

The division of problems and combination of subproblems

b)

Whether the sub problems overlap or not

c)

The way we solve the base case

d)

The depth of recurrence

48.

If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memorization

d)

Greedy

49.

Which of the following problems is NOT solved using dynamic programming?

a)

0/1 knapsack problem

b)

Matrix chain multiplication problem

c)

Edit distance problem

d)

Fractional knapsack problem

50.

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}

51.

For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.

a)

True

b)

False

52.

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

a)

170

b)

200

c)

160

d)

90

53.

Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?

a)

10*20

b)

20*30

c)

10*30

d)

10*20*30

54.

Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

a)

6

b)

7

c)

8

d)

9

55.

In which of the following cases will the edit distance between two strings be zero?

a)

When one string is a substring of another

b)

When the lengths of the two strings are equal

c)

When the two strings are equal

d)

The edit distance can never be zero

56.

Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.

a)

True

b)

False

57.

Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?

a)

3

b)

4

c)

5

d)

6

58.

For which of the following pairs of strings is the edit distance maximum?

a)

Sunday & Monday

b)

Monday & Tuesday

c)

Tuesday & Wednesday

d)

Wednesday & Thursday

59.

Which of the following problems is equivalent to the 0-1 Knapsack problem?

a)

You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value

b)

You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized

c)

You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S

d)

None of the mentioned

60.

The 0-1 Knapsack problem can be solved using Greedy algorithm

a)

True

b)

False

61.

Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?

a)

dp[i,j] = 1 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]}

b)

dp[i,j] = 0 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]}

c)

dp[i,j] = 1 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

d)

dp[i,j] = 0 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

62.

What is the time complexity of the dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

a)

O(n)

b)

O(m)

c)

O (m + n)

d)

O(mn)

63.

In Dynamic programming which of the following method does not consist recursion?

a)

memoization

b)

merging

c)

tabulation

d)

none

64.

0/1 knapsack is based on _________ method

a)

greedy method

b)

dynamic programming

c)

divide and conquer

d)

branch and bound

65.

Minimum number of platforms required for trains is

Lists of arrival time and departure time.

Arrival: {900, 940, 950, 1100, 1500, 1800}

Departure: {910, 1200, 1120, 1130, 1900, 2000}

a)

1

b)

2

c)

3

d)

4

66.

In dynamic programming top-down approach is also known as____

a)

tabulation

b)

memoization

c)

optimization

d)

generalization

67.

_______ guarantees to find the optimal solution of a problem if the solution exists

a)

Dynamic programming

b)

Backtracking

c)

Greedy

d)

None

68.

___________ is a method used to store the results of previous function calls to speed up future calculations.

a)

Optimization

b)

Tabulation

c)

Memoization

d)

None

69.

Identify applications of dynamic programming

a)

Fibonacci number series

b)

Knapsack problem

c)

Longest common subsequence

d)

All

70.

Time complexity of longest common sub string using DP is

a)

O(n*m)

b)

O(n+m)

c)

O(n/m)

d)

O(n-m)

71.

Time complexity of longest increasing sub sequences using DP is

a)

O(n^3)

b)

O(n^2)

c)

O(2^n)

d)

O(3^n)

72.

Formula for longest increasing sub sequence is

a)

LS(i) = 1+ max {LS(j)} ; where j<i and A[i] > A[j]

0 ; Otherwise

b)

LS(i) = 1+ min {LS(j)} ; where j<i and A[i] > A[j]

1 ; Otherwise

c)

LS(i) = 1+ max {LS(j)} ; where j<i and A[i] > A[j]

1 ; Otherwise

d)

LS(i) = 1+ max {LS(j)} ; where j>i and A[i] <A[j]

1 ; Otherwise

73.

Which of the following standard algorithms is not Dynamic Programming based

a)

Bellman–Ford Algorithm for single source shortest path

b)

Floyd Warshall Algorithm for all pairs shortest paths

c)

0-1 Knapsack problem

d)

Prim's Minimum Spanning Tree

74.

Which of the following is/are property/properties of a dynamic programming problem?

a)

Optimal substructure

b)

Overlapping subproblems

c)

Distinct Subproblems

d)

Combinatorial

75.

Which technique can be used to get the nth fibonacci term?

a)

Recursion

b)

Dynamic Programming

c)

Both

76.

A greedy algorithm can be used to solve all the dynamic programming problems.

a)

True

b)

False

77.

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called __________

a)

Dynamic Programming

b)

Divide and Conquer

c)

Recursion

d)

Greedy Technique

78.

The 0/1 Knapsack problem belongs to which domain of problems?

a)

NP Complete

b)

Linear Solution

c)

Sorting

d)

Optimization

79.

What is the space complexity of the following dynamic programming implementation of the Knapsack problem?

a)

O(n)

b)

O(n+W)

c)

O(nW)

d)

O(n²)

80.

Which of the following greedy strategies may give the optimal solution for 0-1 knapsack problem?

a)

Largest profit first

b)

Lightest item first

c)

Heaviest item first

d)

Largest profit per unit weight first

81.

Given a Weighted graph G, Floyd's Algorithm finds

a)

Single source shortest path

b)

All pairs shortest path

c)

Minimum Spanning Tree

d)

Transitive closure

82.

Which of the following recurrence formula is correct for all n>k>0

a)

C(n,k) = C(n-1,k-1) + C(n-1, k) & C(n, 0) = C(n, n )= 1

b)

C(n,k)=C(n-1,k-1)+C(n,k-1) & C(0,n) = C(n,n) = 1

c)

C(n,k)=C(n-1,k-1)+C(n-1,k) & C(0,n) = C(n,n) = 1

d)

C(n,k)=C(n-1,k-1)+C(n-1,k) & C(n,0) = C(n,n) = 0

83.

A sequence of values in a column of DP table for an instance of the knapsack problem is always non-decreasing

a)

True

b)

False

84.

Which of the following problems is NOT solved using dynamic programming?

a)

0/1 knapsack problem

b)

Matrix chain multiplication problem

c)

Edit distance problem

d)

Fractional knapsack problem

85.

A greedy algorithm can be used to solve all the dynamic programming problems.

a)

True

b)

False

86.

Dynamic programming differs from the greedy method since the greedy method produces only one feasible solution, which may or may not be optimal, while dynamic programming produces all possible sub-problems at most once, one of which guaranteed to be optimal.

a)

True

b)

False

87.

What are 2 things required in order to successfully use the dynamic programming technique?

a)

Optimal sub structure and overlapping sub problems

b)

A problem that can’t be sub divided and is complex

c)

Non overlapping sub problems and intervals

d)

Recursion and a problem that is complex

88.

Dynamic Programming is often used for (choose all that apply):

a)

Optimization problems that involve making a choice that leave one or more subproblems to be solved.

b)

Problems previously solved using divide and conquer that have over lapping subproblems

c)

Non polynomial solution problems

d)

Subproblems where resources are shared

89.

If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memorization

d)

Greedy

90.

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

a)

170

b)

200

c)

160

d)

90

91.

Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

a)

6

b)

7

c)

8

d)

9

92.

In which of the following cases will the edit distance between two strings be zero?

a)

When one string is a substring of another

b)

When the lengths of the two strings are equal

c)

When the two strings are equal

d)

The edit distance can never be zero

93.

Which of the following problems is equivalent to the 0-1 Knapsack problem?

a)

You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value

b)

You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized

c)

You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S

d)

None of the mentioned

94.

The 0-1 Knapsack problem can be solved using Greedy algorithm

a)

True

b)

False

95.

What is the time complexity of the dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

a)

O(n)

b)

O(m)

c)

O (m + n)

d)

O(mn)

96.

In Greedy method we get ________ Feasible solutions

a)

one

b)

more than one

c)

zero

d)

hundred

97.

Which of the following is true about Huffman Coding.

a)

Huffman coding may become lossy in some cases

b)

Huffman Codes may not be optimal lossless codes in some cases

c)

In Huffman coding, no code is prefix of any other code.

d)

All

98.

How do you move through a Huffman tree?

a)

0 = right 1= left

b)

1 = left 2 = right

c)

0 = left 1 = right

d)

0 = middle 1 = back

99.

Knapsack problem is an example of ________ problem

a)

Maximize

b)

Minimize

c)

Neutralized

d)

Balanced

100.

Which is optimal value in the case of job sequence problem Item : 1 2 3 4 5..

Profit : 20 15 10 5 1

Deadline : 2 2 3 3 3

a)

1,3,4

b)

1,2,4

c)

4,2,3

d)

1,5,2

DAA 2023- 2024 Test 4

Total questions: 100

Worksheet time: 1hrs 11mins

Similar Resources on Wayground