Data Structures u0026 Algorithms: Recursive Problem Solving Quiz

Challenge your understanding of complex data structures, recursion types, and backtracking algorithms such as N-Queens, Rat in a Maze, and Sudoku solving. This quiz is designed to test both theoretical knowledge and practical application.

1. Identifying Recursion Type

   Which of the following code snippets exemplifies tail recursion in computing the factorial of n?

   1. A function that returns n * factorial(n - 1) with no accumulator.
   2. A function that executes factorial(n - 1) after multiplying n.
   3. A function that always recurses before performing multiplication.
   4. A function that calls itself with n - 1 and multiplies after returning.
   5. A function that passes an accumulator parameter and returns accumulator when n == 0.

2. N-Queens Constraint Checking

   In the classic N-Queens problem, which condition must be checked to ensure a queen at row i, column j does not attack an already-placed queen at row k, column l?

   1. i == l or j == k
   2. i == k or j == l or |i-k| == |j-l|
   3. i + l == k + j
   4. i == j or k == l or i + j == k + l
   5. Only i != k and j != l

3. Rat in a Maze Pathfinding

   Suppose you are solving the Rat in a Maze problem using backtracking; which of the following ensures all possible unique paths are explored?

   1. Never marking visited cells.
   2. Marking all unvisited neighboring cells as walls.
   3. Marking visited cells and unmarking them after all recursive calls from that cell are finished.
   4. Exploring only the right and down directions.
   5. Returning immediately after finding one valid path.

4. Recursion Stack Insight

   During the solution of the Sudoku problem with backtracking, what does the recursion stack represent at any point?

   1. The sequence of backtracking steps from the start of the board to the current empty cell being filled.
   2. The collection of fully filled rows only.
   3. A heap of valid Sudoku configurations.
   4. The set of all possible numbers in the entire grid.
   5. The list of all empty cells left to fill in the puzzle.

5. Space Complexity with Recursion

   What is the worst-case auxiliary space complexity of a standard recursive solution for the N-Queens problem on an n×n board?

   1. O(n!)
   2. O(1)
   3. O(n^2)
   4. O(log n)
   5. O(n)

6. Detecting Base Case Errors

   In backtracking algorithms, which consequence is most likely if the base case is missing or incorrect?

   1. The solution will always be optimal regardless.
   2. All valid solutions will be skipped.
   3. It will simply process fewer recursive calls.
   4. There will be a minor reduction in performance but still correct output.
   5. The recursion may result in an infinite loop or stack overflow.

7. Head vs. Tail Recursion Output

   Given a function that prints numbers from n down to 1 recursively, why does head recursion print output in descending order while tail recursion can be made to print in ascending order?

   1. Because both always print in descending order.
   2. Because tail recursion always uses loops internally.
   3. In head recursion, actions happen after recursion returns; in tail recursion, actions occur before the recursive call.
   4. Because head recursion uses more memory than tail recursion.
   5. Because tail recursion and head recursion are equivalent.

8. Efficiency in Sudoku Solvers

   Which optimization is most effective in improving the efficiency of recursive backtracking Sudoku solvers?

   1. Checking only the first row for conflicts.
   2. Randomly filling empty cells first.
   3. Ignoring filled cells and considering only empty ones.
   4. Tracking used numbers in rows, columns, and subgrids using bit masks or sets.
   5. Trying numbers sequentially from 1 to 9 without checking constraints.

9. State Representation in Backtracking

   When implementing backtracking for N-Queens, which data structure most efficiently represents which columns are under attack?

   1. A single integer for all columns.
   2. A matrix representing the entire board.
   3. A list of row indices.
   4. A stack containing queen objects.
   5. A boolean array of size n.

10. Pruning in Recursion

    In the context of backtracking, what does the term 'pruning' specifically refer to?

    1. Dividing the problem into two equal halves before recursing.
    2. Reducing time complexity by sorting the input.
    3. Skipping recursive calls that cannot possibly lead to a solution based on constraints.
    4. Trimming whitespace from input data before recursion.
    5. Recursively deleting nodes in a tree data structure.