Back to course

Exercise 1

Backtracking

Algorithm AnalysisMathematical StatementsMedium Difficulty

Exam Format & Expectations

Backtracking questions typically give you an algorithm and ask you to:

  1. Determine output values - What does the algorithm return for specific inputs?
  2. Write mathematical statement - Formally describe what the algorithm computes
  3. State preconditions - When is the input valid?

Key: The mathematical statement should be precise. Use set notation, quantifiers (∀, ∃), and formal definitions.

Past Exam Example: N-Queens Counting (2024 Resit)

Given Algorithm:

countQueens(n, row, positions)
if row = n: return 1 count = 0 for col in 0..n-1: if isSafe(positions, row, col): positions[row] = col count = count + countQueens(n, row + 1, positions) return count

Question 1a: What is countQueens(4, 0, [])?

Determine the exact output value.

Full Solution(3/3 points)

Answer: countQueens(4, 0, []) = 2

Reasoning: For n=4, there are exactly 2 valid N-queens placements:

Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .
Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .

Question 1b: Mathematical Statement

Write a formal mathematical statement describing what countQueens(n, 0, []) computes.

Full Solution(7/7 points)

Mathematical Statement:

Let countQueens(n, 0, []) = |{Q ∈ Pn | Q is a valid n-queens placement}|

where:

  • • Pn = { permutations of (0,1,...,n-1) }
  • • A placement Q = (q0, q1, ..., qn-1) is valid if:
  • - qi represents the column of the queen in row i
  • - ∀i,j ∈ {0,...,n-1}, i ≠ j: queens at (i,qi) and (j,qj) don't attack
  • - No two queens share a diagonal: |i-j| ≠ |qi-qj|

Note: The algorithm counts the number of ways to place n non-attacking queens on an n×n chessboard, where each row and column contains exactly one queen.

Pattern: Permutation Generation

Common Pattern

Many backtracking algorithms generate permutations. For a function generateAll(A):

generateAll(A) = { all permutations of elements in A }

Formally: generateAll(A) = { p : A → A | p is a bijection }

Example: Permutation Counter

function countPerms(A, used, k): if k = |A|: return 1 count = 0 for i in 0..|A|-1: if not used[i]: used[i] = true count += countPerms(A, used, k+1) used[i] = false return count

Answer: countPerms(A, [false,...,false], 0) = |A|!

Answer: generateAll(A) computes all permutations of A

Exam Strategy & Tips

Do This ✓

  • • Trace the algorithm with a small example first
  • • Use proper set notation: {x ∈ S | P(x)}
  • • Define all variables clearly
  • • State preconditions: "for all n ≥ 1"
  • • Be precise about what's being counted/found

Avoid This ✗

  • • Don't describe HOW the algorithm works
  • • Don't use informal language
  • • Don't forget edge cases (n=0, empty input)
  • • Don't mix implementation with specification
  • • Don't use ambiguous notation

Pro tip: The mathematical statement is usually worth 70% of the points. Spend time making it precise and complete.

Back to overviewNext: Greedy Choice