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 6, Modulus: 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.
- String Matching Algorithm
- Shortest Path Algorithm
- Minimum spanning tree Algorithm
- Approximation Algorithm
0 Comments