Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 9
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!)
Correct Answer:
A
Chapter: 9
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
Correct Answer:
C
Chapter: 9
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
Correct Answer:
A
Chapter: 9
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
Correct Answer:
B
Chapter: 9
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
Correct Answer:
B
Chapter: 9
Q306:
The term "NP" stands for:
A. Non-polynomial
B. Non-deterministic polynomial
C. Non-permissive
D. Non-positive
Correct Answer:
B
Chapter: 9
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
Correct Answer:
B
Chapter: 9
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
Correct Answer:
B
Chapter: 9
Q309:
A decision problem's output can be categorized as:
A. Numeric values
B. Graphical data
C. True/False
D. Arrays
Correct Answer:
C
Chapter: 9
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
Correct Answer:
A
Chapter: 9
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
Correct Answer:
B
Chapter: 9
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
Correct Answer:
C
Chapter: 9
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
Correct Answer:
B
Chapter: 9
Q314:
What is the Independent Set Problem concerned with?
A. Adjacent vertices selection
B. Vertex coloring
C. Graph traversal
D. Shortest path calculation
Correct Answer:
A
Chapter: 9
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
Correct Answer:
B
Chapter: 9
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
Correct Answer:
B
Chapter: 9
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
Correct Answer:
B
Chapter: 9
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
Correct Answer:
B
Chapter: 9
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
Correct Answer:
C
Chapter: 9
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
Correct Answer:
A