โ˜‘ MCQ PRACTICE

Design and Analysis of Algorithms Unit 3

Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.

๐Ÿ“š Design and Analysis of Algorithms
๐Ÿ“– Unit 3
๐ŸŽฏ MCQs
Design and Analysis of Algorithms MCQs - Unit 3

Design and Analysis of Algorithms MCQs - Unit 3

1

Dynamic programming is based on the principle of

A randomness
B greed
C recursion only
D optimality
Correct Answer optimality
2

Dynamic programming is useful when the subproblems

A are completely independent
B do not exist
C overlap
D are always unsolvable
Correct Answer overlap
3

Dynamic programming stores the results of subproblems in

A the compiler
B a table
C the keyboard buffer
D the printer
Correct Answer a table
4

In the 0/1 knapsack problem, each item is

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
5

The time complexity of the dynamic programming solution of the 0/1 knapsack problem is

A O(n)
B O(log n)
C O(W) only
D O(nW)
Correct Answer O(nW)
6

The recurrence of the 0/1 knapsack problem is V[i, w] =

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])
7

The algorithm used to find all-pairs shortest paths is

A Kruskal
B Prim
C Quick sort
D Floydโ€“Warshall
Correct Answer Floydโ€“Warshall
8

The time complexity of Floydโ€“Warshall's algorithm is

A O(nยณ)
B O(n)
C O(nยฒ)
D O(n log n)
Correct Answer O(nยณ)
9

Floydโ€“Warshall's algorithm can handle negative edge weights as long as there is no

A positive cycle
B self-loop of weight zero
C negative cycle
D vertex of degree one
Correct Answer negative cycle
10

In Floyd's algorithm, A^k(i, j) =

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)}
11

The dynamic programming solution of the travelling salesperson problem takes

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
12

The travelling salesperson problem asks for the shortest tour that

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
13

An optimal binary search tree is a binary search tree that

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
14

The dynamic programming solution of the optimal binary search tree problem takes

A O(n) time
B O(log n) time
C O(nยณ) time
D O(1) time
Correct Answer O(nยณ) time
15

In the optimal binary search tree recurrence, c(i, j) is computed as

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)
16

The reliability design problem aims to

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
17

The reliability of a system with stages in series is the

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
18

If a stage has m copies of a device with reliability r in parallel, its reliability is

A 1 โˆ’ (1 โˆ’ r)^m
B r^m
C m ร— r
D r โˆ’ m
Correct Answer 1 โˆ’ (1 โˆ’ r)^m
19

Which of the following problems is solved correctly by dynamic programming but NOT by the greedy method?

A Fractional knapsack problem
B Minimum spanning tree
C 0/1 knapsack problem
D Huffman coding
Correct Answer 0/1 knapsack problem
20

Storing the results of subproblems so that they are not recomputed is called

A recursion only
B memoization
C backtracking
D hashing of passwords
Correct Answer memoization
21

Computing the n-th Fibonacci number with dynamic programming takes

A O(n) time
B O(2โฟ) time
C O(n!) time
D O(log log n) time
Correct Answer O(n) time
22

The optimal substructure property means that

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
23

The travelling salesperson problem is

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
24

The space required by Floydโ€“Warshall's algorithm is

A O(1)
B O(n)
C O(nยฒ)
D O(nยณ)
Correct Answer O(nยฒ)
25

A bottom-up dynamic programming solution fills the table

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
โ† Back to All MCQs