Study Glance
☑ MCQ PRACTICE

Design and Analysis of Algorithms Unit 5

Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.

📚 Design and Analysis of Algorithms
📖 Unit 5
🎯 MCQs

Design and Analysis of Algorithms - Unit-5

1
What is the main purpose of the branch and bound method in optimization problems?
ATo find the best solution by exploring all possible solutions.
BTo eliminate non-promising solutions through bounding.
CBoth A and B.
DNone of the above.
Correct Answer Both A and B.
2
How does the 'branching' part work in the branch and bound method?
ABy dividing the problem into smaller subproblems.
BBy calculating the upper and lower bounds of the problem.
CBy selecting the optimal solution directly.
DBy increasing the complexity of the problem.
Correct Answer By dividing the problem into smaller subproblems.
3
What is the role of 'bounding' in the branch and bound method?
ATo estimate the best-case scenario of the solution.
BTo reduce the number of subproblems to be examined.
CBoth A and B.
DNeither A nor B.
Correct Answer Both A and B.
4
Which type of search is typically used in the branch and bound algorithm?
ADepth-first search
BBreadth-first search
CLinear search
DBoth A and B
Correct Answer Both A and B
5
What is a common bounding technique used in the branch and bound method?
AGreedy technique
BDynamic programming
CBacktracking
DDivide and conquer
Correct Answer Greedy technique
6
In the context of solving the 0/1 Knapsack problem, what does the 'bound' represent?
AThe minimum weight of items to be included in the knapsack.
BThe maximum value that can be achieved from the items left after branching.
CThe total weight capacity of the knapsack.
DThe number of items that can be chosen.
Correct Answer The maximum value that can be achieved from the items left after branching.
7
Which property ensures that branch and bound is effective in reducing the solution space?
ACompleteness
BOptimality
CLower bounding
DUpper bounding
Correct Answer Lower bounding
8
How does the branch and bound method differ from a pure backtracking approach?
ABranch and bound uses bounds to prune the search space, while backtracking does not.
BBranch and bound is used only for optimization problems, while backtracking is not.
CBranch and bound is a type of greedy algorithm, while backtracking is not.
DThere is no difference; they are the same.
Correct Answer Branch and bound uses bounds to prune the search space, while backtracking does not.
9
What is the main characteristic of the LC Branch and Bound method in the context of the 0/1 Knapsack problem?
AIt prioritizes branches based on the highest profit.
BIt prioritizes branches based on the least cost or best bound.
CIt examines branches in a random order.
DIt prioritizes branches based on the shortest processing time.
Correct Answer It prioritizes branches based on the least cost or best bound.
10
How does the LC Branch and Bound method estimate the bound for a node in the 0/1 Knapsack problem?
ABy considering the total weight of items left.
BBy calculating the maximum profit obtainable from the items that could still fit.
CBy the number of items remaining.
DBy the minimum weight of the remaining items.
Correct Answer By calculating the maximum profit obtainable from the items that could still fit.
11
What does 'cost' refer to in the LC Branch and Bound method for the 0/1 Knapsack problem?
AThe actual weight of items included in the knapsack.
BThe total value or profit lost by not including certain items.
CThe estimated profit if all remaining items were included.
DThe cumulative profit of the path leading to the current node.
Correct Answer The cumulative profit of the path leading to the current node.
12
How does the FIFO method manage the state space tree in branch and bound?
ABy prioritizing deeper nodes in the tree.
BBy exploring nodes in the sequence they were generated.
CBy eliminating all nodes that exceed the knapsack's weight limit.
DBy reordering nodes based on descending profit values.
Correct Answer By exploring nodes in the sequence they were generated.
13
What is the primary advantage of using the LC Branch and Bound method for the 0/1 Knapsack Problem?
AIt ensures that the maximum profit is achieved quickly.
BIt minimizes the number of nodes explored.
CIt always processes the most promising node first.
DIt simplifies calculations for large datasets.
Correct Answer It always processes the most promising node first.
14
What is the main benefit of using FIFO Branch and Bound for the 0/1 Knapsack Problem?
AIt is less likely to miss the optimal solution.
BIt provides a quicker solution than other methods.
CIt is easier to implement than other branch and bound methods.
DIt reduces the overall memory usage compared to other methods.
Correct Answer It is less likely to miss the optimal solution.
15
What does the class P represent in computational theory?
AProblems that are solvable in polynomial time by a non-deterministic Turing machine.
BProblems that are solvable in polynomial time by a deterministic Turing machine.
CProblems that are unsolvable even by a Turing machine.
DProblems that can only be solved by quantum computers.
Correct Answer Problems that are solvable in polynomial time by a deterministic Turing machine.
16
Which class includes decision problems that can be verified in polynomial time by a deterministic Turing machine, given a correct solution to the problem?
AP
BNP
CNPC
DNP-hard
Correct Answer NP
17
What is the relationship between P and NP classes?
AP is a subset of NP.
BNP is a subset of P.
CP and NP are completely disjoint sets.
DP and NP are equivalent and contain the same set of problems.
Correct Answer P is a subset of NP.
18
Which of the following statements is true regarding NP-complete problems?
AThey are the easiest problems in NP.
BThey are the hardest problems in NP.
CThey cannot be verified in polynomial time.
DThey do not belong to the class NP.
Correct Answer They are the hardest problems in NP.
19
If a polynomial time algorithm is found for one NP-complete problem, what is the implication for other NP-complete problems?
AThey all remain NP-complete.
BThey all can also be solved in polynomial time.
CThey all become unsolvable.
DNo implications can be drawn.
Correct Answer They all can also be solved in polynomial time.
20
Which of the following problems is a known NP-complete problem?
ABinary search
BTraveling Salesperson Problem (TSP)
CMatrix multiplication
DCalculating the greatest common divisor (GCD)
Correct Answer Traveling Salesperson Problem (TSP)
21
Which statement best describes the NP class?
AIt contains problems that are solved and verified in non-polynomial time.
BIt includes problems that are solved in polynomial time and verified in non-polynomial time.
CIt includes problems whose solutions can be verified in polynomial time.
DIt includes only unsolvable problems.
Correct Answer It includes problems whose solutions can be verified in polynomial time.
22
What does the question "Is P equal to NP?" ask?
AWhether every problem that can be verified in polynomial time can also be solved in polynomial time.
BWhether problems in NP are also in P.
CWhether all problems in P are also NP-complete.
DWhether non-deterministic Turing machines are faster than deterministic ones.
Correct Answer Whether every problem that can be verified in polynomial time can also be solved in polynomial time.
23
What defines a problem as NP-Hard?
AIt can be solved in polynomial time on a non-deterministic Turing machine.
BIt is at least as hard as the hardest problems in NP.
CIt is verifiable in polynomial time but not solvable in polynomial time.
DIt is the subset of problems in P.
Correct Answer It is at least as hard as the hardest problems in NP.
24
Which of the following is a characteristic of an NP-Complete problem?
AIt is solvable in polynomial time.
BIt is both in NP and NP-Hard.
CIt cannot be verified or solved in polynomial time.
DIt has no known polynomial-time algorithm.
Correct Answer It is both in NP and NP-Hard.
25
According to Cook’s theorem, which statement is true?
AThe Boolean satisfiability problem (SAT) is NP-Complete.
BAll problems in P are also in NP.
CNP-complete problems are solvable in polynomial time.
DP equals NP.
Correct Answer The Boolean satisfiability problem (SAT) is NP-Complete.
26
What is the significance of Cook’s theorem in computational complexity?
AIt proves that all problems in NP are also in P.
BIt established that the SAT problem can be reduced to any other problem in NP, demonstrating the concept of NP-completeness.
CIt provides a solution to the P vs NP problem.
DIt shows that NP-Hard problems are solvable in polynomial time.
Correct Answer It established that the SAT problem can be reduced to any other problem in NP, demonstrating the concept of NP-completeness.
27
Which type of reduction is typically used to prove that a problem is NP-Complete?
APolynomial-time reduction
BExponential-time reduction
CLinear-time reduction
DLogarithmic-time reduction
Correct Answer Polynomial-time reduction
28
If a new problem X can be polynomial-time reduced from an NP-Complete problem, what can be concluded about problem X?
AX is in P.
BX is NP-Hard.
CX is easier than NP-Complete problems.
DX cannot be NP-Complete.
Correct Answer X is NP-Hard.
29
Which problem did Cook use to prove his theorem regarding NP-completeness?
AGraph Coloring
BTraveling Salesperson Problem
CKnapsack Problem
DBoolean Satisfiability Problem (SAT)
Correct Answer Boolean Satisfiability Problem (SAT)
30
What does it imply if an NP-Hard problem can be solved in polynomial time?
AP is equal to NP.
BNP-complete problems can no longer be considered difficult.
CThe problem was misclassified and is actually in P.
DBoth A and B are correct.
Correct Answer Both A and B are correct.
31
Which of the following statements is true about NP-Hard problems?
AThey include all problems in NP.
BThey are a subset of NP-Complete problems.
CThey are not necessarily in NP, but are at least as hard as NP-Complete problems.
DThey are easier than NP-Complete problems.
Correct Answer They are not necessarily in NP, but are at least as hard as NP-Complete problems.
32
Which of the following statements is true regarding the 0/1 Knapsack Problem?
AIt can be solved in linear time.
BIt is a polynomial-time solvable problem.
CIt is an NP-complete problem.
DIt does not require dynamic programming or recursion.
Correct Answer It is an NP-complete problem.
33
What is a characteristic of the TSP?
AIt is NP-hard.
BIt can be solved in polynomial time.
CIt does not require the path to return to the origin.
DIt usually involves directed acyclic graphs.
Correct Answer It is NP-hard.
34
Let A be an NP-complete problem and B and C be two another problems not known to be in NP, B is polynomial-time reducible to A and A is polynomial-time reducible to C, which one of the following statement is true?
AC is NP-Complete.
BC is NP-Hard.
CB is NP-Complete.
DB is NP-Hard.
Correct Answer C is NP-Complete.
35
Naveen and Madhu have been asked to show that a certain problem X is NP-complete. Naveen shows a polynomial-time reduction from the SAT problem to X and Madhu shows a polynomial time-reduction from X to SAT, which of the following can be inferred from these reductions
AX is NP-hard but not NP-Complete.
BX is NP but not NP-Complete.
CX is NP-Complete.
DX is neither NP-hard nor NP.
Correct Answer X is NP-Complete.

Fill in the Blanks

36 Branch and Bound is a technique used to solve __________ problems.
Correct Answer Optimization
37 The main idea behind Branch and Bound is to __________ the search space into smaller subspaces and __________ solutions in a systematic way.
Correct Answer Divide, evaluate (or explore)
38 In Branch and Bound, the problem is typically divided into __________ and each subproblem is solved __________.
Correct Answer Subproblems, sequentially
39 The "bound" in Branch and Bound refers to an __________ that serves as a criterion for pruning branches in the search space.
Correct Answer Upper bound
40 The process of Branch and Bound involves comparing current __________ with the __________ obtained so far.
Correct Answer Bounds (or estimates), best solution
41 NP-Hard problems are problems that are at least as hard as any problem in __________.
Correct Answer NP (Non-deterministic Polynomial time)
42 An NP-Complete problem that is often used in theoretical computer science to demonstrate NP-completeness is the __________ problem.
Correct Answer Boolean Satisfiability (SAT)
43 The Cook-Levin theorem states that __________ is NP-complete.
Correct Answer Boolean Satisfiability (SAT)
44 A problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time. This property is known as __________.
Correct Answer Polynomial-time reduction (or polynomial-time Turing reduction)
45 The traveling salesman problem (TSP) is a classic example of an NP-__________ problem.
Correct Answer Complete
46 The decision version of the knapsack problem is NP-__________.
Correct Answer Complete
47 A problem that is both NP and NP-hard is __________.
Correct Answer NP-complete
← Back to All MCQs