ADA Module-5 Quiz 2024

What is the N Queens problem?

• The N Queens problem is about placing N kings on an N×N chessboard.

• The N Queens problem is about placing N rooks on an N×N chessboard.

• The N Queens problem is about placing N chess queens on an N×N chessboard so that no two queens attack each other.

• The N Queens problem is about placing N pawns on an N×N chessboard.

What is the Subset Sum problem?

• The Subset Sum problem is only applicable to strings, not integers.

• The Subset Sum problem involves finding the largest number in a set of integers.

• The Subset Sum problem is related to sorting a list of integers in ascending order.

• The Subset Sum problem is a classic computer science problem that involves finding a subset of a given set of integers that adds up to a specific target sum.

How can backtracking be applied to solve the Subset Sum problem?

• Apply backtracking to skip exploring subsets and directly calculate the sum

• Apply backtracking to only include elements greater than the target sum

• Apply backtracking to sort the elements before exploring subsets

• Apply backtracking to recursively explore all possible subsets by including or excluding elements based on the target sum.

Describe the Branch and Bound algorithm.

• Branch and Bound algorithm systematically enumerates all candidate solutions and uses bounding functions to eliminate suboptimal solutions.

• Branch and Bound algorithm does not use bounding functions to eliminate suboptimal solutions.

• Branch and Bound algorithm only considers the first solution found.

• Branch and Bound algorithm randomly selects solutions without considering optimality.

What is the Discrete Knapsack problem?

• The Discrete Knapsack problem is a combinatorial optimization problem where the goal is to maximize the total value of items placed into a knapsack without exceeding its capacity.

• The Discrete Knapsack problem aims to minimize the total value of items placed into a knapsack

• The Discrete Knapsack problem is related to sorting algorithms

• The Discrete Knapsack problem involves solving linear equations

Provide an example scenario where the Discrete Knapsack problem can be applied.

• Organizing a bookshelf by genre

• Stealing valuable items from a house with limited carrying capacity.

• Fishing for different types of fish

• Collecting stamps from around the world

What is the Continuous Knapsack problem?

• The Continuous Knapsack problem involves sorting items in the knapsack based on their weight.

• The Continuous Knapsack problem involves selecting items for the knapsack randomly.

• The Continuous Knapsack problem involves minimizing the total value of items in the knapsack without exceeding the weight capacity.

• The Continuous Knapsack problem involves maximizing the total value of items in the knapsack without exceeding the weight capacity.

Differentiate between the Discrete and Continuous Knapsack problems.

• Discrete Knapsack: Items can be selected in whole numbers. Continuous Knapsack: Items can be selected in whole numbers.

• Discrete Knapsack: Items can be selected in fractions. Continuous Knapsack: Items can only be selected in whole numbers.

• Discrete Knapsack: Items can be selected in decimals. Continuous Knapsack: Items can be selected in whole numbers.

• Discrete Knapsack: Items can only be selected in whole numbers. Continuous Knapsack: Fractions of items can be selected.

How is the N Queens problem related to backtracking?

• The N Queens problem involves sorting numbers in ascending order

• Backtracking is used to find the optimal solution quickly

• Backtracking is used to systematically explore all possible configurations of the chessboard to find a solution where N queens can be placed without threatening each other.

• Backtracking guarantees a solution without any constraints

Discuss the trade-offs between greedy algorithms and dynamic programming in solving the Knapsack problem.

• Greedy algorithms always provide the optimal solution for the Knapsack problem.

• Dynamic programming provides an optimal solution for the Knapsack problem, while greedy algorithms might give suboptimal solutions.

• Dynamic programming is less efficient than greedy algorithms in solving the Knapsack problem.

• Greedy algorithms and dynamic programming are interchangeable methods for solving the Knapsack problem.