Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 9
Q321:
For a given boolean formula in 3-CNF, the output graph has _______ vertices.
A. 2k
B. 3k
C. k
D. 4k
Correct Answer:
B
Chapter: 9
Q322:
What is k in the context of the Independent Set Problem?
A. The number of edges in G
B. The number of vertices in G
C. The number of clauses in F
D. The number of independent sets in G
Correct Answer:
C
Chapter: 9
Q323:
In a 3-CNF formula, each clause must contain _______. at least one true literal
A. at least one false literal
B. exactly one true literal
C. exactly three literals
Correct Answer:
A
Chapter: 9
Q324:
The transformation from 3SAT to IS runs in _______. exponential time
A. linear time
B. polynomial time
C. quadratic time
Correct Answer:
C
Chapter: 9
Q325:
A valid heuristic for coping with NP-completeness is to _______. always find the optimal solution
A. ignore the problem entirely
B. use brute-force search
C. apply general search methods
Correct Answer:
D
Chapter: 9
Q326:
Fill in the blank: The Independent Set Problem arises from selection problems with _______. mutual exclusions
A. linear constraints
B. weight limits
C. none of the above
Correct Answer:
A
Chapter: 9
Q327:
Which of the following best describes a heuristic?
A. A guaranteed optimal solution
B. A strategy for finding a valid solution with no guarantees
C. An exact solution method
D. A measure of algorithm performance
Correct Answer:
B
Chapter: 9
Q328:
The reduction from 3SAT to IS uses _______ to represent each literal.
A. vertices
B. edges
C. weights
D. colors
Correct Answer:
A
Chapter: 9
Q329:
The output of the function 3SAT-TO-IS is a _______. matrix and integer
A. graph and integer
B. list and integer
C. set and integer
Correct Answer:
B
Chapter: 9
Q330:
An approximation algorithm is desirable because it _______. runs in polynomial time and guarantees optimality
A. runs in polynomial time and provides a near-optimal solution
B. runs in linear time and guarantees optimality
C. runs in exponential time and guarantees a solution
Correct Answer:
B