Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q301: A polynomial time algorithm must have a running time of:
- A: O(n^k) for some k
- B: O(2^n)
- C: O(n log n)
- D: O(n!)
View Answer
A
Q302: If a problem is NP-hard, it means:
- A: It is easy to solve
- B: It is impossible to solve
- C: Solving it implies all NP problems can be solved in polynomial time
- D: It has no solutions
View Answer
C
Q303: The Hamiltonian cycle problem is an example of:
- A: A decision problem
- B: An optimization problem
- C: A polynomial problem
- D: An easy problem
View Answer
A
Q304: In the context of verification algorithms, a certificate is:
- A: A graphical representation
- B: A solution provided for verification
- C: A mathematical proof
- D: A decision tree
View Answer
B
Q305: The class NP-complete consists of problems that are:
- A: All solvable in linear time
- B: Decision problems that are NP-hard
- C: Always solvable in polynomial time
- D: Only solvable by brute force
View Answer
B
Q306: The term "NP" stands for:
- A: Non-polynomial
- B: Non-deterministic polynomial
- C: Non-permissive
- D: Non-positive
View Answer
B
Q307: Which of the following problems is known to be NP-complete?
- A: Sorting
- B: Graph Isomorphism
- C: Finding the minimum spanning tree
- D: Searching an array
View Answer
B
Q308: The 3-color problem involves:
- A: Finding a Hamiltonian cycle
- B: Assigning colors to graph vertices
- C: Solving a knapsack problem
- D: Finding the shortest path in a graph
View Answer
B
Q309: A decision problem's output can be categorized as:
- A: Numeric values
- B: Graphical data
- C: True/False
- D: Arrays
View Answer
C
Q310: What is the relationship between class P and class NP?
- A: P is a subset of NP
- B: NP is a subset of P
- C: P and NP are disjoint
- D: They are identical
View Answer
A