DSA_Unit5

Backtracking is a general algorithmic technique that is used to solve problems by:

• Dividing a problem into smaller subproblems

• Exploring all possible options and discarding the ones that fail

• Finding the shortest path between two nodes

• Sorting elements in ascending order

Which data structure is primarily used in the backtracking algorithm?

• Queue

• Stack

• Heap

• Linked List

Which of the following problems is best solved using backtracking?

• Binary Search

• 8-Queens Problem

• Merge Sort

• Kruskal’s Algorithm

The 8-Queens problem is a classic example of which algorithmic technique?

• Dynamic Programming

• Greedy Algorithm

• Backtracking

• Divide and Conquer

In the 8-Queens problem, what is the main constraint?

• No two queens should be in the same row

• No two queens should be in the same column

• No two queens should attack each other

• All of the above

Which of the following problems is NOT typically solved using backtracking?

• Graph Coloring

• Sudoku Solver

• Prim’s Algorithm

• Hamiltonian Cycle

What is the time complexity of the backtracking algorithm for solving the N-Queens problem?

• O(N)

• O(N²)

• O(N!)

• O(2ⁿ)

Which method is used in backtracking to discard a solution when it is determined to be infeasible?

• Pruning

• Sorting

• Partitioning

• Greedy Selection

The Sum of Subsets problem requires selecting subsets such that:

• The sum of elements in the subset equals a given number

• The subset contains the maximum number of elements

• The subset contains only even numbers

• The subset forms a geometric sequence

Which approach is used in Graph Coloring problems?

• Divide and Conquer

• Dynamic Programming

• Backtracking

• Hashing