Tutorials
PPTs
Lecture Notes
Objective Questions
Lab ProgramsObjective Type Questions & Answers
Design and Analysis of Algorithms MCQs - Unit-5
1. What is the main purpose of the branch and bound method in optimization problems?
A . To find the best solution by exploring all possible solutions.
B . To eliminate non-promising solutions through bounding.
C . Both A and B.
D . None of the above.
2. How does the `branching` part work in the branch and bound method?
A . By dividing the problem into smaller subproblems.
B . By calculating the upper and lower bounds of the problem.
C . By selecting the optimal solution directly.
D . By increasing the complexity of the problem.
3. What is the role of `bounding` in the branch and bound method?
A . To estimate the best-case scenario of the solution.
B . To reduce the number of subproblems to be examined.
C . Both A and B.
D . Neither A nor B.
4. Which type of search is typically used in the branch and bound algorithm?
A . Depth-first search
B . Breadth-first search
C . Linear search
D . Both A and B
5. What is a common bounding technique used in the branch and bound method?
A . Greedy technique
B . Dynamic programming
C . Backtracking
D . Divide and conquer
6. In the context of solving the 0/1 Knapsack problem, what does the `bound` represent?
A . The minimum weight of items to be included in the knapsack.
B . The maximum value that can be achieved from the items left after branching.
C . The total weight capacity of the knapsack.
D . The number of items that can be chosen.
7. Which property ensures that branch and bound is effective in reducing the solution space?
A . Completeness
B . Optimality
C . Lower bounding
D . Upper bounding
8. How does the branch and bound method differ from a pure backtracking approach?
A . Branch and bound uses bounds to prune the search space, while backtracking does not.
B . Branch and bound is used only for optimization problems, while backtracking is not.
C . Branch and bound is a type of greedy algorithm, while backtracking is not.
D . There is no difference; they are the same.
9. What is the main characteristic of the LC Branch and Bound method in the context of the 0/1 Knapsack problem?
A . It prioritizes branches based on the highest profit.
B . It prioritizes branches based on the least cost or best bound.
C . It examines branches in a random order.
D . It prioritizes branches based on the shortest processing time.
10. How does the LC Branch and Bound method estimate the bound for a node in the 0/1 Knapsack problem?
A . By considering the total weight of items left.
B . By calculating the maximum profit obtainable from the items that could still fit.
C . By the number of items remaining.
D . By the minimum weight of the remaining items.
11. What does `cost` refer to in the LC Branch and Bound method for the 0/1 Knapsack problem?
A . The actual weight of items included in the knapsack.
B . The total value or profit lost by not including certain items.
C . The estimated profit if all remaining items were included.
D . 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?
A . By prioritizing deeper nodes in the tree.
B . By exploring nodes in the sequence they were generated.
C . By eliminating all nodes that exceed the knapsack`s weight limit.
D . By reordering nodes based on descending profit values.
13. What is the primary advantage of using the LC Branch and Bound method for the 0/1 Knapsack Problem?
A . It ensures that the maximum profit is achieved quickly.
B . It minimizes the number of nodes explored.
C . It always processes the most promising node first.
D . It simplifies calculations for large datasets.
14. What is the main benefit of using FIFO Branch and Bound for the 0/1 Knapsack Problem?
A . It is less likely to miss the optimal solution.
B . It provides a quicker solution than other methods.
C . It is easier to implement than other branch and bound methods.
D . It reduces the overall memory usage compared to other methods.
15. What does the class P represent in computational theory?
A . Problems that are solvable in polynomial time by a non-deterministic Turing machine.
B . Problems that are solvable in polynomial time by a deterministic Turing machine.
C . Problems that are unsolvable even by a Turing machine.
D . Problems that can only be solved by quantum computers.
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?
A . P
B . NP
C . NPC
D . NP-hard
17. What is the relationship between P and NP classes?
A . P is a subset of NP.
B . NP is a subset of P.
C . P and NP are completely disjoint sets.
D . P and NP are equivalent and contain the same set of problems.
18. Which of the following statements is true regarding NP-complete problems?
A . They are the easiest problems in NP.
B . They are the hardest problems in NP.
C . They cannot be verified in polynomial time.
D . They do not belong to the class NP.
19. If a polynomial time algorithm is found for one NP-complete problem, what is the implication for other NP-complete problems?
A . They all remain NP-complete.
B . They all can also be solved in polynomial time.
C . They all become unsolvable.
D . No implications can be drawn.
20. Which of the following problems is a known NP-complete problem?
A . Binary search
B . Traveling Salesperson Problem (TSP)
C . Matrix multiplication
D . Calculating the greatest common divisor (GCD)
21. Which statement best describes the NP class?
A . It contains problems that are solved and verified in non-polynomial time.
B . It includes problems that are solved in polynomial time and verified in non-polynomial time.
C . It includes problems whose solutions can be verified in polynomial time.
D . It includes only unsolvable problems.
22. What does the question "Is P equal to NP?" ask?
A . Whether every problem that can be verified in polynomial time can also be solved in polynomial time.
B . Whether problems in NP are also in P.
C . Whether all problems in P are also NP-complete.
D . Whether non-deterministic Turing machines are faster than deterministic ones.
23. What defines a problem as NP-Hard?
A . It can be solved in polynomial time on a non-deterministic Turing machine.
B . It is at least as hard as the hardest problems in NP.
C . It is verifiable in polynomial time but not solvable in polynomial time.
D . It is the subset of problems in P.
24. Which of the following is a characteristic of an NP-Complete problem?
A . It is solvable in polynomial time.
B . It is both in NP and NP-Hard.
C . It cannot be verified or solved in polynomial time.
D . It has no known polynomial-time algorithm.
25. According to Cook’s theorem, which statement is true?
A . The Boolean satisfiability problem (SAT) is NP-Complete.
B . All problems in P are also in NP.
C . NP-complete problems are solvable in polynomial time.
D . P equals NP.
26. What is the significance of Cook’s theorem in computational complexity?
A . It proves that all problems in NP are also in P.
B . It established that the SAT problem can be reduced to any other problem in NP, demonstrating the concept of NP-completeness.
C . It provides a solution to the P vs NP problem.
D . It shows that NP-Hard problems are solvable in polynomial time.
27. Which type of reduction is typically used to prove that a problem is NP-Complete?
A . Polynomial-time reduction
B . Exponential-time reduction
C . Linear-time reduction
D . Logarithmic-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?
A . X is in P.
B . X is NP-Hard.
C . X is easier than NP-Complete problems.
D . X cannot be NP-Complete.
29. Which problem did Cook use to prove his theorem regarding NP-completeness?
A . Graph Coloring
B . Traveling Salesperson Problem
C . Knapsack Problem
D . Boolean Satisfiability Problem (SAT)
30. What does it imply if an NP-Hard problem can be solved in polynomial time?
A . P is equal to NP.
B . NP-complete problems can no longer be considered difficult.
C . The problem was misclassified and is actually in P.
D . Both A and B are correct.
31. Which of the following statements is true about NP-Hard problems?
A . They include all problems in NP.
B . They are a subset of NP-Complete problems.
C . They are not necessarily in NP, but are at least as hard as NP-Complete problems.
D . They are easier than NP-Complete problems.
32. Which of the following statements is true regarding the 0/1 Knapsack Problem?
A . It can be solved in linear time.
B . It is a polynomial-time solvable problem.
C . It is an NP-complete problem.
D . It does not require dynamic programming or recursion.
33. What is a characteristic of the TSP?
A . It is NP-hard.
B . It can be solved in polynomial time.
C . It does not require the path to return to the origin.
D . It usually involves directed acyclic graphs.
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?
A . C is NP-Complete.
B . C is NP-Hard.
C . B is NP-Complete.
D . B is NP-Hard.
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 SAP, which of the following can be inferred from these reductions
A . X is NP-hard but not NP-Complete.
B . X is NP but not NP-Complete.
C . X is NP-Complete.
D . X is neither NP-hard nor NP.
Fill in the Blanks
36. Branch and Bound is a technique used to solve __________ problems.
37. The main idea behind Branch and Bound is to __________ the search space into smaller subspaces and __________ solutions in a systematic way.
38. In Branch and Bound, the problem is typically divided into __________ and each subproblem is solved __________.
39. The "bound" in Branch and Bound refers to an __________ that serves as a criterion for pruning branches in the search
40. The process of Branch and Bound involves comparing current __________ with the __________ obtained so far.
41. NP-Hard problems are problems that are at least as hard as any problem in __________.
42. An NP-Complete problem that is often used in theoretical computer science to demonstrate NP-completeness is the __________ problem.
43. The Cook-Levin theorem states that __________ is NP-complete.
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 __________.
45. The traveling salesman problem (TSP) is a classic example of an NP-__________ problem.
46. The decision version of the knapsack problem is NP-__________.
47. A problem that is both NP and NP-hard is __________.
Relevant Materials :
☞ Design and Analysis of Algorithms MCQs - Unit-1 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-2 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-3 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-4 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-5 - [ DAA ]
Similar Materials :
☞ R - Programming MCQs - Unit-1 - [ R-Programming ]
☞ R - Programming MCQs - Unit-2 - [ R-Programming ]
☞ R - Programming MCQs - Unit-3 - [ R-Programming ]
☞ R - Programming MCQs - Unit-4 - [ R-Programming ]
☞ R - Programming MCQs - Unit-5 - [ R-Programming ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-1 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-2 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-3 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-4 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-5 - [ FLAT ]
☞ PPS MCQs - Unit-1 - [ PPS ]
☞ PPS MCQs - Unit-2 - [ PPS ]
☞ PPS MCQs - Unit-3 - [ PPS ]
☞ PPS MCQs - Unit-4 - [ PPS ]
☞ PPS MCQs - Unit-5 - [ PPS ]
☞ Object Oriented Programming through Java MCQs - Unit-1 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-2 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-3 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-4 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-5 - [ OOP_JAVA ]
☞ Software Engineering MCQs - Unit-1 - [ SE ]
☞ Software Engineering MCQs - Unit-2 - [ SE ]
☞ Software Engineering MCQs - Unit-3 - [ SE ]
☞ Software Engineering MCQs - Unit-4 - [ SE ]
☞ Software Engineering MCQs - Unit-5 - [ SE ]
☞ Data Mining MCQs - Unit-1 - [ DM ]
☞ Data Mining MCQs - Unit-2 - [ DM ]
☞ Data Mining MCQs - Unit-3 - [ DM ]
☞ Data Mining MCQs - Unit-4 - [ DM ]
☞ Data Mining MCQs - Unit-5 - [ DM ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-1 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-2 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-3 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-4 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-5 - [ COA ]
☞ Data Structures Objective Type Question Bank-Unit-1 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-2 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-3 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-4 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-5 - [ DS ]
☞ Database Management System Objective Type Question Bank-Unit-1 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-2 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-3 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-4 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-5 - [ DBMS ]
☞ Cyber Forensics Objective Type Question Bank-Part-2 - [ Cyber Forensics ]
☞ Cyber Forensics Objective Type Question Bank-Part-1 - [ Cyber Forensics ]
☞ Java Programming Objective Type Question Bank - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-1 - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-2 - [ Java Programming ]