Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q321: For a given boolean formula in 3-CNF, the output graph has _______ vertices.
- A: 2k
- B: 3k
- C: k
- D: 4k
View Answer
B
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
View Answer
C
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
- D:
View Answer
A
Q324: The transformation from 3SAT to IS runs in _______. exponential time
- A: linear time
- B: polynomial time
- C: quadratic time
- D:
View Answer
C
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
- D:
View Answer
D
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
- D:
View Answer
A
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
View Answer
B
Q328: The reduction from 3SAT to IS uses _______ to represent each literal.
- A: vertices
- B: edges
- C: weights
- D: colors
View Answer
A
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
- D:
View Answer
B
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
- D:
View Answer
B