FUNDAMENTALS OF ALGORITHMS - UNIT 5 MCQS

What is the main idea behind backtracking?

• The main idea behind backtracking is to incrementally build candidates for solutions and abandon them if they are not valid.

• The main idea of backtracking is to find all possible solutions without any constraints.

• Backtracking is a method to solve problems by using random guesses.

• Backtracking focuses on solving problems by brute force without any optimization.

How does the 8-Queens problem illustrate backtracking?

• The 8-Queens problem uses a greedy algorithm to find a solution.

• The 8-Queens problem demonstrates backtracking by exploring and retracting placements of queens to find a valid configuration.

• The 8-Queens problem requires placing all queens in a single row.

• The 8-Queens problem is solved by randomly placing queens on the board.

What is the base case in a backtracking algorithm?

• The base case is the starting point of the algorithm.

• The base case is the condition that stops the recursion.

• The base case is the maximum depth of recursion.

• The base case is the first solution found during backtracking.

Explain the concept of pruning in backtracking.

• Pruning refers to the technique of selecting the best path without eliminating others.

• Pruning is the process of adding more paths to explore in backtracking.

• Pruning is the process of eliminating paths in backtracking that cannot lead to a valid solution.

• Pruning is a method used to increase the number of solutions found in backtracking.

What is the time complexity of the 8-Queens problem?

• O(N^2)

• O(N log N)

• O(2^N)

• O(N!)

How can backtracking be applied to the Sum of Subsets problem?

• Backtracking eliminates all subsets that exceed the target sum immediately.

• Backtracking is used to sort the subsets before summing them.

• Backtracking explores all subsets to find those that sum to a target.

• Backtracking only finds the maximum subset sum.

What is the difference between backtracking and dynamic programming?

• Backtracking uses a greedy approach to find solutions.

• Dynamic programming only works for linear problems.

• Backtracking explores all possible solutions, while dynamic programming optimizes by storing results of subproblems.

• Backtracking is faster than dynamic programming.

Describe a real-world application of graph coloring.

• Scheduling tasks in a way that avoids conflicts.

• Designing logos with multiple color schemes.

• Creating art using various colors and patterns.

• Coloring maps to represent different countries.

What are the constraints in the 8-Queens problem?

• No two queens can share the same row, column, or diagonal.

• Each queen must be placed in a different color square.

• Queens can attack any piece on the board.

• Queens can only be placed in the same row.

How can you represent a graph for graph coloring?

• A graph with vertices and edges where vertices represent items to color and edges represent conflicts.

• A graph with only vertices and no edges.

• A linear sequence of colors without any connections.

• A table listing colors without any graph structure.