ADVANCED DATA STRUCTURES AND ALGORITHMS ANALYSIS CLASS TEST-6

The Branch and Bound technique is primarily used for

• Solving differential equations

• Optimization problems

• Simulation problems

• Sorting problems

In the Branch and Bound method, a “bound” is used to

• Determine the search direction

• Eliminate suboptimal solutions

• Randomly select branches

• Sort the nodes

The Branch and Bound approach for 0/1 Knapsack uses

• Upper and lower bounds of profit

• Random selection of items

• Only weight constraints

• None of the above

The Travelling Salesperson Problem is

• Polynomial time solvable

• NP-Complete

• NP-Hard

• Both B and C

The TSP decision problem asks whether

• There exists a tour with cost ≤ K

• There exists a tour with minimum cost

A problem is said to be NP-Complete if

• It is both in NP and NP-Hard

• It can be solved in polynomial time

• It is not in NP

• None of the above

NP stands for

• Non-polynomial

• Non-deterministic Polynomial time

• Numeric Polynomial

• Nominal Polynomial

Cook’s theorem is important because it

• Defines a new graph theory concept

• Shows that SAT is NP-Complete

• Proves that all problems are NP-Hard

• Defines the concept of backtracking

Every NP-Complete problem is

• Solvable in constant time

• At least as hard as every problem in NP

• Easier than polynomial problems

• None of the above

In the Clique Decision Problem, the goal is to

• Find the largest clique in a graph

• Determine if a clique of size k exists

• Minimize the number of edges

• Maximize the number of vertices