Design and Analysis of Algorithms
1. The time required to find shortest path in a graph with n vertices and e edges is
Select one:
a. O (n2) Correct
b. O (n)
c. O (e)
d. O (e2)
Feedback
The correct answer is: O (n2)
2. A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] != Y[j-1]
Select one:
a. expr2 ≡ max(l(i-1,j-1),l(i,j))
b. expr1 ≡ l(i, j-1)
c. expr2 ≡ max(l(i-1, j), l(i, j-1)) Correct
d. expr1 ≡ l(i-1, j) + 1
Feedback
The correct answer is: expr2 ≡ max(l(i-1, j), l(i, j-1))
3.In Ford-Fulkerson algorithm, flow of the augmenting path is selected based on
Select one:
a. cf(p) =min{ cf (u,v):(u,v)is in p }
b. cf(p) =max{ cf (u,v):(u,v)is in p }
c. cf(p) =min{ cf (u,v):(u,v)is in f-P } Incorrect
d. cf(p) =max{ cf (u,v):(u,v)is in f-P }
Feedback
The correct answer is: cf(p) =min{ cf (u,v):(u,v)is in p }
4. what is an optimal Huffman code for alphabet b of the following set of frequencies a: 45, b:13, c:12, d:16, e:9, f:5
Select one:
a. 001
b. 100
c. 111
d. 101 Correct
Feedback
The correct answer is: 101
5. Match the following:
List – I List – II
1 Quick Sort a Divide and Conquer
2 Graph colouring b Greedy
3 String editing c Dynamic
Programming
4 Prim’s Algorithm d Back tracking
Select one:
1-a, 2-c, 3-b, 4-d
1-b, 2-a, 3-d, 4-c Incorrect
1-a, 2-d, 3-c, 4-b
None of these
6. kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST
Select one:
a. vertex,edges
b. vertex,vertex
c. edges,vertex Correct
d. edges,edges
Feedback
The correct answer is: edges,vertex
7.Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
Select one:
a. Π is NP-complete Correct
b. Π is NP-hard but not NP-complete
c. Π is in NP, but is not NP-complete
d. Π is neither NP-hard, nor in NP
Feedback
The correct answer is: Π is NP-complete
8.Consider the following two problems of graph.
1) Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle.
2) Given a graph, find if the graph has a cycle that visits every edge exactly once. Which of the following is true about above two problems
Select one:
a. Both problems belong to NP complete set
b. Both problems belong to P set
c. Problem 1 belongs to P set and 2 belongs to NP Complete set
d. Problem 1 belongs NP Complete set and 2 belongs to P Correct
Feedback
The correct answer is: Problem 1 belongs NP Complete set and 2 belongs to P
9.If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
Select one:
a. O(log n)
b. O(n2)
c. O(n log n)
d. O(n3) Correct
Feedback
The correct answer is: O(n3)
10.To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
Select one:
a. B-Tree
b. Heap
c. Stack
d. Queue Correct
Feedback
The correct answer is: Queue
11.For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for memory table, and ______time to determine the optimal load, for N objects and W as the capacity of KNAPSACK.
Select one:
a. O(N), O(NW)
b. O(N+W), O(NW)
c. O(NW), O(N+W) Correct
d. O(NW), O(N)
Feedback
The correct answer is: O(NW), O(N+W)
12.Match the following
Group A Group B
a) Dijkstra's single shortest path p) Dynamic Programming
b) Bellmen Ford's single shortest path algorithm q) Backtracking
c) Floyd Warshell's all pair shortest path algorithm r) Greedy Algorithm
Select one:
a. a-p, b-p, c-p
b. a-r, b-p, c-p Correct
c. a-r, b-q, c-p
d. a-p, b-r, c-q
Feedback
The correct answer is: a-r, b-p, c-p
13.A simple Graph G = L U R, set of 2 non-empty vertices and each vertex from L has an edge to atleast one vertex of R, is called as
Select one:
a. Bipartite Graph
b. Bifocal graph Incorrect
c. Complete graph
d. Flow-network graph
Feedback
The correct answer is: Bipartite Graph
14. Find the Running Time of the fastest algorithm to calculate the shortest path between any two vertices of a graph where all edges have equal weights.
Select one:
0(V log2V+E )
0 (E+V) Correct
0(V log V2+E)
0 (V+E) log2V
Feedback
Your answer is correct.
The correct answer is: 0 (E+V)
15.In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by
Select one:
a. Dijkstra’s algorithm starting from S.
b. Performing a BFS starting from S Correct
c. Performing a DFS starting from S.
d. Warshall’s algorithm
Feedback
The correct answer is: Performing a BFS starting from S
16. Which of the following statement(s)is / are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable
from the source.
Select one:
a. Neither P nor Q
b. P Only
c. Both P and Q
d. Q Only Correct
Feedback
The correct answer is: Q Only
17. There are 5 items as follows
Items
wi
vi
Item1
5 pounds
30$
Item2
10 pounds
20$
Item3
20 pounds
100$
Item4
30 pounds
90$
Item5
40 pounds
160$
The knapsack can hold 60 pounds find the optimal solution
Design and Analysis of Algorithms
Select one:
a. 250$
b. 270 $
c. 260 $ Correct
d. 290$
Feedback
The correct answer is: 260 $
18. In flow networks Residual capacity Cf (u,v)=
Select one:
a. t(u,v) – s(u,v)
b. s(u,v) – t(u, v)
c. c(u,v) – f(u,v) Correct
d. f(u, v) – c(u,v)
Feedback
The correct answer is: c(u,v) – f(u,v)
19. Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
Select one:
a. 19000 Correct
b. 248000
c. 25000
d. 44000
Feedback
The correct answer is: 19000
20. Consider the decision problem 2CNFSAT defined as follows:
Select one:
a. NP-hard, but not NP-complete.
b. solvable in polynomial time by reduction to directed graph reachability
c. solvable in constant time since any input instance is satisfiable. Incorrect
d. NP-Complete.
Feedback
The correct answer is: solvable in polynomial time by reduction to directed graph reachability
1. The time required to find shortest path in a graph with n vertices and e edges is
Select one:
a. O (n2) Correct
b. O (n)
c. O (e)
d. O (e2)
Feedback
The correct answer is: O (n2)
2. A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] != Y[j-1]
Select one:
a. expr2 ≡ max(l(i-1,j-1),l(i,j))
b. expr1 ≡ l(i, j-1)
c. expr2 ≡ max(l(i-1, j), l(i, j-1)) Correct
d. expr1 ≡ l(i-1, j) + 1
Feedback
The correct answer is: expr2 ≡ max(l(i-1, j), l(i, j-1))
3.In Ford-Fulkerson algorithm, flow of the augmenting path is selected based on
Select one:
a. cf(p) =min{ cf (u,v):(u,v)is in p }
b. cf(p) =max{ cf (u,v):(u,v)is in p }
c. cf(p) =min{ cf (u,v):(u,v)is in f-P } Incorrect
d. cf(p) =max{ cf (u,v):(u,v)is in f-P }
Feedback
The correct answer is: cf(p) =min{ cf (u,v):(u,v)is in p }
4. what is an optimal Huffman code for alphabet b of the following set of frequencies a: 45, b:13, c:12, d:16, e:9, f:5
Select one:
a. 001
b. 100
c. 111
d. 101 Correct
Feedback
The correct answer is: 101
5. Match the following:
List – I List – II
1 Quick Sort a Divide and Conquer
2 Graph colouring b Greedy
3 String editing c Dynamic
Programming
4 Prim’s Algorithm d Back tracking
Select one:
1-a, 2-c, 3-b, 4-d
1-b, 2-a, 3-d, 4-c Incorrect
1-a, 2-d, 3-c, 4-b
None of these
6. kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST
Select one:
a. vertex,edges
b. vertex,vertex
c. edges,vertex Correct
d. edges,edges
Feedback
The correct answer is: edges,vertex
7.Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
Select one:
a. Π is NP-complete Correct
b. Π is NP-hard but not NP-complete
c. Π is in NP, but is not NP-complete
d. Π is neither NP-hard, nor in NP
Feedback
The correct answer is: Π is NP-complete
8.Consider the following two problems of graph.
1) Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle.
2) Given a graph, find if the graph has a cycle that visits every edge exactly once. Which of the following is true about above two problems
Select one:
a. Both problems belong to NP complete set
b. Both problems belong to P set
c. Problem 1 belongs to P set and 2 belongs to NP Complete set
d. Problem 1 belongs NP Complete set and 2 belongs to P Correct
Feedback
The correct answer is: Problem 1 belongs NP Complete set and 2 belongs to P
9.If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time.
Select one:
a. O(log n)
b. O(n2)
c. O(n log n)
d. O(n3) Correct
Feedback
The correct answer is: O(n3)
10.To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
Select one:
a. B-Tree
b. Heap
c. Stack
d. Queue Correct
Feedback
The correct answer is: Queue
11.For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for memory table, and ______time to determine the optimal load, for N objects and W as the capacity of KNAPSACK.
Select one:
a. O(N), O(NW)
b. O(N+W), O(NW)
c. O(NW), O(N+W) Correct
d. O(NW), O(N)
Feedback
The correct answer is: O(NW), O(N+W)
12.Match the following
Group A Group B
a) Dijkstra's single shortest path p) Dynamic Programming
b) Bellmen Ford's single shortest path algorithm q) Backtracking
c) Floyd Warshell's all pair shortest path algorithm r) Greedy Algorithm
Select one:
a. a-p, b-p, c-p
b. a-r, b-p, c-p Correct
c. a-r, b-q, c-p
d. a-p, b-r, c-q
Feedback
The correct answer is: a-r, b-p, c-p
13.A simple Graph G = L U R, set of 2 non-empty vertices and each vertex from L has an edge to atleast one vertex of R, is called as
Select one:
a. Bipartite Graph
b. Bifocal graph Incorrect
c. Complete graph
d. Flow-network graph
Feedback
The correct answer is: Bipartite Graph
14. Find the Running Time of the fastest algorithm to calculate the shortest path between any two vertices of a graph where all edges have equal weights.
Select one:
0(V log2V+E )
0 (E+V) Correct
0(V log V2+E)
0 (V+E) log2V
Feedback
Your answer is correct.
The correct answer is: 0 (E+V)
15.In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by
Select one:
a. Dijkstra’s algorithm starting from S.
b. Performing a BFS starting from S Correct
c. Performing a DFS starting from S.
d. Warshall’s algorithm
Feedback
The correct answer is: Performing a BFS starting from S
16. Which of the following statement(s)is / are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable
from the source.
Select one:
a. Neither P nor Q
b. P Only
c. Both P and Q
d. Q Only Correct
Feedback
The correct answer is: Q Only
17. There are 5 items as follows
Items
wi
vi
Item1
5 pounds
30$
Item2
10 pounds
20$
Item3
20 pounds
100$
Item4
30 pounds
90$
Item5
40 pounds
160$
The knapsack can hold 60 pounds find the optimal solution
Design and Analysis of Algorithms
Select one:
a. 250$
b. 270 $
c. 260 $ Correct
d. 290$
Feedback
The correct answer is: 260 $
18. In flow networks Residual capacity Cf (u,v)=
Select one:
a. t(u,v) – s(u,v)
b. s(u,v) – t(u, v)
c. c(u,v) – f(u,v) Correct
d. f(u, v) – c(u,v)
Feedback
The correct answer is: c(u,v) – f(u,v)
19. Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
Select one:
a. 19000 Correct
b. 248000
c. 25000
d. 44000
Feedback
The correct answer is: 19000
20. Consider the decision problem 2CNFSAT defined as follows:
Select one:
a. NP-hard, but not NP-complete.
b. solvable in polynomial time by reduction to directed graph reachability
c. solvable in constant time since any input instance is satisfiable. Incorrect
d. NP-Complete.
Feedback
The correct answer is: solvable in polynomial time by reduction to directed graph reachability
No comments:
Post a Comment