Design and Analysis of Algorithms MCQs - Unit 5
A
only sorting problems
B
only searching problems
C
only printing problems
D
optimization problems
Correct Answer
optimization problems
A
the highest cost
B
the oldest entry
C
the newest entry
D
the least cost
Correct Answer
the least cost
A
stack
B
heap only
C
table of keys
D
queue
Correct Answer
queue
A
queue
B
linked list only
C
stack
D
graph
Correct Answer
stack
A
less than the best solution found so far
B
zero
C
greater than or equal to the best solution found so far
D
negative
Correct Answer
greater than or equal to the best solution found so far
A
a sorted array
B
a reduced cost matrix
C
a hash table
D
a binary tree
Correct Answer
a reduced cost matrix
A
squared
B
ignored
C
doubled
D
negated
Correct Answer
negated
A
in polynomial time by a deterministic algorithm
B
only in exponential time
C
only by non-deterministic machines
D
by no algorithm
Correct Answer
in polynomial time by a deterministic algorithm
A
only in exponential time by any algorithm
B
by no algorithm
C
in polynomial time by a non-deterministic algorithm
D
in logarithmic time only
Correct Answer
in polynomial time by a non-deterministic algorithm
A
push, pop and peek
B
read, write and seek
C
choice, failure and success
D
open, close and flush
Correct Answer
choice, failure and success
A
it can be solved in linear time
B
every problem in NP can be reduced to it in polynomial time
C
it is in P
D
it has no input
Correct Answer
every problem in NP can be reduced to it in polynomial time
A
both in NP and NP-hard
B
in P only
C
neither in NP nor NP-hard
D
NP-hard only
Correct Answer
both in NP and NP-hard
A
the satisfiability (SAT) problem is NP-complete
B
sorting is NP-complete
C
P is a subset of NP only
D
binary search is NP-hard
Correct Answer
the satisfiability (SAT) problem is NP-complete
A
travelling salesperson problem
B
knapsack problem
C
satisfiability (SAT)
D
graph coloring
Correct Answer
satisfiability (SAT)
A
P = NP
B
P â NP
C
NP = EXP
D
all problems are unsolvable
Correct Answer
P = NP
A
Binary search
B
Sorting an array
C
Hamiltonian cycle
D
Finding the maximum element
Correct Answer
Hamiltonian cycle
A
Travelling salesperson problem
B
Hamiltonian cycle
C
Graph coloring (decision, k âĨ 3)
D
Single-source shortest path with non-negative weights
Correct Answer
Single-source shortest path with non-negative weights
A
polynomial-time reducible to problem B
B
harder than B always
C
unrelated to B
D
solved by B in constant time only
Correct Answer
polynomial-time reducible to problem B
A
in P
B
unsolvable
C
NP-complete
D
linear-time solvable
Correct Answer
NP-complete
A
P
B
NP
C
the set of all problems
D
the set of languages
Correct Answer
NP
A
P â NP
B
NP â P
C
P âĐ NP is empty
D
NP = EXP
Correct Answer
P â NP
A
a graph is connected
B
an array is sorted
C
a Boolean formula can be made true by some assignment of values
D
a matrix is square
Correct Answer
a Boolean formula can be made true by some assignment of values
A
uses bounds on the cost to prune and is used for optimization
B
never prunes nodes
C
uses only recursion
D
does not use a state space tree
Correct Answer
uses bounds on the cost to prune and is used for optimization
A
dead nodes
B
answer nodes only
C
root nodes only
D
live nodes
Correct Answer
live nodes
A
the problem to sorting
B
a known NP-hard problem to it
C
the problem to binary search
D
the problem to a constant
Correct Answer
a known NP-hard problem to it
Fill in the Blanks
26
Branch and bound is mainly used to solve ______ problems.
Correct Answer
optimization
27
In LC branch and bound, the next E-node is the live node with the ______ cost.
Correct Answer
least
28
FIFO branch and bound uses a ______.
Correct Answer
queue
29
LIFO branch and bound uses a ______.
Correct Answer
stack
30
In the branch and bound solution of the TSP, the lower bound is found by reducing the cost ______.
Correct Answer
matrix
31
P stands for ______ time.
Correct Answer
Polynomial
32
NP stands for ______ Polynomial.
Correct Answer
Non-deterministic
33
A non-deterministic algorithm uses the functions choice, failure and ______.
Correct Answer
success
34
Cook's theorem states that the ______ problem is NP-complete.
Correct Answer
satisfiability (SAT)
35
A problem is NP-complete if it is in NP and is ______.
Correct Answer
NP-hard
36
The first problem proved to be NP-complete was ______.
Correct Answer
satisfiability (SAT)
37
If any NP-complete problem can be solved in polynomial time, then P = ______.
Correct Answer
NP
38
A âĪp B means that A is polynomial-time ______ to B.
Correct Answer
reducible
39
NP-hard problems are at least as ______ as every problem in NP.
Correct Answer
hard
40
The Hamiltonian cycle decision problem is ______-complete.
Correct Answer
NP