### Ticker

6/recent/ticker-posts

# CSE408 Design & Analysis Of Algorithms Practice MCQs

CSE408 Practice MCQs.

DESIGN & ANALYSIS OF ALGORITHMS Practice MCQs 19 Questions.

1. Which approach is based on computing the distance between each pair of distinct points and finding a pair with the smallest distance?

Bruteforce.

2. If n is the length of text(T) and m is the length of the pattern(P) identify the correct pre-processing algorithm. (where q is a suitable modulus to reduce the complexity) p=0; t0=0;

for i=1 to m do p=(dp + P[i])mod q t0=(dt0+T[i])mod q

3. Given a pattern of length- 5 window, find the valid match in the given text.

Pattern: 2 1 9 3 6Modulus: 21, Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21, Text: 9 2 7 2 1 8 3 0 5 7 1 2 1 2 1 9 3 6 2 3 9 7

13-17

4. What is the worst case running time of Rabin Karp Algorithm?

Theta((n-m+1)m)

5. Spurious hit in the given text:-T=123456 ,P=34,q=11 is not found in shift s

2

6. Spurious hit in the given text:-T=13579 ,P=35,q=11 is found in shift s

0.2,3.

7. To compute t0 in Rabin Karp

t0=(dt0+T[i])%q.

8. A simple path is a

Sequence of adjacent (connected by an edge) vertices that starts with u and ends with v and every edge of a path is distinct.

9. A tree is a

It is a connected acyclic graph.

10. What is the time complexity for finding the height of the binary tree?

h = O(log n)

11. What is a full binary tree?

Each node has exactly zero or two children.

12. The number of edges from the root to the node is called ____ of the tree.

Depth.

13.If there are 5 vertices whose edges are  edges = [[0, 1], [1, 2], [2, 3], [3, 4]]. Find the connected component .

1.

14.Efficient algorithm requires less computational ___

Meomory and running.

15. If f(x) = 3x2 + x3logx, then f(x) is?

O(x3).

16. If f(x) = (x3 – 1) / (3x + 1) then f(x) is?

0(x)2.

17. Examples of O(1) algorithms are______.

• Multiplying two numbers.
• Assigning same value to a variable.
• Displaying same integer on console
• All of the above.
18.The big-theta notation for function f(n) = 2n3 + n – 1 is?

n3

19. What is a Rabin and Karp Algorithm?
• String Matching Algorithm
• Shortest Path Algorithm
• Minimum spanning tree Algorithm
• Approximation Algorithm