Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q311: What type of problem is characterized by an output of "yes" or "no"?
- A: Optimization problem
- B: Decision problem
- C: Graph problem
- D: Polynomial problem
View Answer
B
Q312: In the fish tank problem, the goal is to find:
- A: The smallest number of fish types
- B: The largest tank size
- C: The smallest number of tanks needed
- D: The fastest way to clean tanks
View Answer
C
Q313: A unique Hamiltonian cycle can be verified by:
- A: Listing all possible cycles
- B: Showing a valid Hamiltonian cycle
- C: Counting vertices
- D: Showing it is not Hamiltonian
View Answer
B
Q314: What is the Independent Set Problem concerned with?
- A: Adjacent vertices selection
- B: Vertex coloring
- C: Graph traversal
- D: Shortest path calculation
View Answer
A
Q315: An independent set of size 4 implies _______.
- A: four vertices are adjacent
- B: four vertices are not adjacent
- C: four vertices are selected from a single cluster
- D: four vertices must be colored differently
View Answer
B
Q316: What does it mean if a problem is NP-complete?
- A: It can be solved in polynomial time
- B: No known polynomial-time solution exists
- C: All problems are reducible to it
- D: It's solvable only by brute force
View Answer
B
Q317: In the Independent Set Problem, the verification process can be done in _______.
- A: linear time
- B: polynomial time
- C: quadratic time
- D: exponential time
View Answer
B
Q318: The reduction from 3SAT to Independent Set shows that _______. 3SAT is more complex than IS
- A: IS is as complex as 3SAT
- B: 3SAT cannot be solved
- C: IS has a polynomial solution
- D:
View Answer
B
Q319: The vertices in an independent set must _______.
- A: share an edge
- B: be adjacent to each other
- C: not share an edge
- D: be in the same cluster
View Answer
C
Q320: In the context of the Independent Set Problem, the adjacency matrix is used for _______. defining edges between vertices
- A: storing the independent set
- B: listing vertices' weights
- C: none of the above
- D:
View Answer
A