Design and Analysis of Algorithms MCQs - Unit 3
A
randomness
B
greed
C
recursion only
D
optimality
Correct Answer
optimality
A
are completely independent
B
do not exist
C
overlap
D
are always unsolvable
Correct Answer
overlap
A
the compiler
B
a table
C
the keyboard buffer
D
the printer
Correct Answer
a table
A
divisible into fractions
B
taken any number of times
C
always taken
D
either taken completely or not taken at all
Correct Answer
either taken completely or not taken at all
A
O(n)
B
O(log n)
C
O(W) only
D
O(nW)
Correct Answer
O(nW)
A
min(V[iโ1, w], v_i)
B
V[iโ1, w] + V[i, wโ1]
C
v_i ร w_i
D
max(V[iโ1, w], v_i + V[iโ1, w โ w_i])
Correct Answer
max(V[iโ1, w], v_i + V[iโ1, w โ w_i])
A
Kruskal
B
Prim
C
Quick sort
D
FloydโWarshall
Correct Answer
FloydโWarshall
A
O(nยณ)
B
O(n)
C
O(nยฒ)
D
O(n log n)
Correct Answer
O(nยณ)
A
positive cycle
B
self-loop of weight zero
C
negative cycle
D
vertex of degree one
Correct Answer
negative cycle
A
min{A^(kโ1)(i, j), A^(kโ1)(i, k) + A^(kโ1)(k, j)}
B
max{A^(kโ1)(i, j), A^(kโ1)(i, k)}
C
A^(kโ1)(i, j) ร A^(kโ1)(k, j)
D
A^(kโ1)(i, k) โ A^(kโ1)(k, j)
Correct Answer
min{A^(kโ1)(i, j), A^(kโ1)(i, k) + A^(kโ1)(k, j)}
A
O(n) time
B
O(n log n) time
C
O(nยณ) time
D
O(nยฒ 2โฟ) time
Correct Answer
O(nยฒ 2โฟ) time
A
visits only half of the cities
B
visits every road once
C
never returns to the start
D
visits every city exactly once and returns to the start
Correct Answer
visits every city exactly once and returns to the start
A
has the minimum expected search cost
B
has maximum height
C
has no keys
D
is always complete
Correct Answer
has the minimum expected search cost
A
O(n) time
B
O(log n) time
C
O(nยณ) time
D
O(1) time
Correct Answer
O(nยณ) time
A
the maximum of all keys
B
the sum of all probabilities only
C
the minimum over k of c(i, kโ1) + c(k, j), plus the weight w(i, j)
D
the product of the keys
Correct Answer
the minimum over k of c(i, kโ1) + c(k, j), plus the weight w(i, j)
A
maximize system reliability under a cost constraint
B
minimize the number of stages
C
maximize the cost
D
remove all devices
Correct Answer
maximize system reliability under a cost constraint
A
sum of the reliabilities
B
product of the reliabilities of its stages
C
minimum cost
D
maximum cost
Correct Answer
product of the reliabilities of its stages
A
1 โ (1 โ r)^m
B
r^m
C
m ร r
D
r โ m
Correct Answer
1 โ (1 โ r)^m
A
Fractional knapsack problem
B
Minimum spanning tree
C
0/1 knapsack problem
D
Huffman coding
Correct Answer
0/1 knapsack problem
A
recursion only
B
memoization
C
backtracking
D
hashing of passwords
Correct Answer
memoization
A
O(n) time
B
O(2โฟ) time
C
O(n!) time
D
O(log log n) time
Correct Answer
O(n) time
A
the solution is always unique
B
an optimal solution contains optimal solutions of its subproblems
C
no subproblems exist
D
the problem has no solution
Correct Answer
an optimal solution contains optimal solutions of its subproblems
A
solvable in O(n) time
B
solvable in O(log n) time
C
not a graph problem
D
NP-hard
Correct Answer
NP-hard
A
O(1)
B
O(n)
C
O(nยฒ)
D
O(nยณ)
Correct Answer
O(nยฒ)
A
starting from the smallest subproblems
B
starting from the largest problem only
C
in random order
D
without any order
Correct Answer
starting from the smallest subproblems
Fill in the Blanks
26
Dynamic programming is based on the principle of ______.
Correct Answer
optimality
27
In the 0/1 knapsack problem, each item is either taken ______ or not taken at all.
Correct Answer
completely
28
The time complexity of the dynamic programming solution of the 0/1 knapsack problem is ______.
Correct Answer
O(nW)
29
The ______ algorithm is used to solve the all-pairs shortest path problem.
Correct Answer
FloydโWarshall
30
The time complexity of FloydโWarshall's algorithm is ______.
Correct Answer
O(nยณ)
31
The dynamic programming solution of the travelling salesperson problem takes ______ time.
Correct Answer
O(nยฒ 2โฟ)
32
OBST stands for Optimal Binary Search ______.
Correct Answer
Tree
33
The reliability of a series system is the ______ of the reliabilities of its stages.
Correct Answer
product
34
A stage with m parallel copies of a device of reliability r has reliability ______.
Correct Answer
1 โ (1 โ r)^m
35
Storing the results of subproblems to avoid recomputation is called ______.
Correct Answer
memoization
36
The ______ substructure property says that an optimal solution contains optimal solutions of its subproblems.
Correct Answer
optimal
37
Computing the n-th Fibonacci number with dynamic programming takes ______ time.
Correct Answer
O(n)
38
FloydโWarshall's algorithm cannot handle a negative ______.
Correct Answer
cycle
39
In the TSP, the tour must return to the ______ city.
Correct Answer
starting
40
Dynamic programming stores the results of overlapping subproblems in a ______.
Correct Answer
table