Backtracking — Practice Set
In the style of 2ILC0 Algorithms (TU/e)
Five problems on backtracking specifications. Work through the questions first;
worked solutions begin on the last pages.
How these problems work. Each problem gives a recursive backtracking algorithm together with
the meaning of its parameters. For every algorithm you are asked to (i) determine the correct initial
call, (ii) trace the algorithm on concrete inputs — often starting from a partial state in the middle of
the recursion — and (iii) give a mathematical specification of what the call computes as a function
of its parameters. One problem also asks you to fill in a missing line of pseudocode.
1. Backtracking specification: 3-Colorability
A proper 3-coloring of an undirected graph G = (V, E) on n vertices is a function f : V → {1, 2, 3}
assigning each vertex v a color f (v) such that the endpoints of every edge get different colors: for
each edge (u, v) ∈ E we have f (u) ̸= f (v). The 3-Colorability problem asks whether a given
graph admits a proper 3-coloring.
The algorithm below receives the adjacency matrix A[1 . . . n, 1 . . . n] of G (so A[i, j] = 1 iff (i, j) ∈ E,
and A[i, j] = 0 otherwise), an array C[1 . . . n] of colors, and an integer k.
Alg ThreeColor(Array A[1 . . . n, 1 . . . n], Array C[1 . . . n], int k)
if (k == n) then // all vertices colored: verify properness
for (i = 1 to n) do
for (j = 1 to n) do
if (A[i, j] == 1 and C[i] == C[j]) then return FALSE
return TRUE
else // assign a color to the next vertex
for (color = 1 to 3) do
C[k+1] = color
if (ThreeColor(A, C, k+1)) then return TRUE
C[k+1] = 0
return FALSE
(1a) [0.25 pt] What should the values of C[1 . . . n] and k be in the initial call, so that for an input
graph with adjacency matrix A the call ThreeColor(A, C, k) correctly determines whether G admits
a proper 3-coloring?
(1b) [0.25 pt] Consider the graph G1 on the right (edges {1-2, 2-3, 3-4, 4-1, 1-3}). What is the result
of running ThreeColor(A, C, k) with
C = [1, 2, 0, 0], k = 2?
1 2
If the algorithm returns a Boolean value, give that value. If it does not, state the
4 3
reason (endless loop? index-out-of-bounds?).
1
, (1c) [0.25 pt] Consider the complete graph K4 (vertices 1, 2, 3, 4, every pair adjacent). What is the
result of running ThreeColor(A, C, k) with
C = [1, 2, 3, 0], k = 3?
1 2
Same instructions as in (1b).
4 3
(1d) [0.75 pt] Give a mathematical statement that captures the output of ThreeColor in terms of
its parameters A, C, and k. It suffices to cover all inputs satisfying the preconditions:
A is the adjacency matrix of a graph G = (V, E) on n vertices;
C is an array of n integers with C[i] ∈ {1, 2, 3} for i ≤ k and C[i] = 0 for i > k;
k is an integer with 0 ≤ k ≤ n.
Your statement should capture how the partial coloring stored in C affects the output for the same
input graph A.
2. Backtracking specification: 0/1 Knapsack (maximum value)
In the 0/1 Knapsack problem we are given n items, where item i has a weight w[i] ≥ 0 and a value
v[i] ≥ 0, together with a capacity W ≥ 0. A selection is a subset of the items; it is feasible if its
total weight is at most W . The goal is the maximum total value of a feasible selection.
The algorithm receives arrays w[1 . . . n] and v[1 . . . n], the capacity W , an array S[1 . . . n] (where
S[i] = 1 means item i is selected and S[i] = 0 means it is not), and an integer k. We write −∞ to
mean “no feasible selection”.
Alg MaxValue(Array w[1 . . . n], Array v[1 . . . n], int W , Array S[1 . . . n], int k)
if (k == n) then // S is a complete selection: evaluate it
int weight = 0; int value = 0
for (i = 1 to n) do
if (S[i] == 1) then { weight = weight + w[i]; value = value + v[i] }
if (weight ≤ W ) then return value
else return −∞
else // decide whether item k+1 is taken
S[k+1] = 0
int best = MaxValue(w, v, W, S, k+1)
S[k+1] = 1
best = max(best, MaxValue(w, v, W, S, k+1))
S[k+1] = 0
return best
2
In the style of 2ILC0 Algorithms (TU/e)
Five problems on backtracking specifications. Work through the questions first;
worked solutions begin on the last pages.
How these problems work. Each problem gives a recursive backtracking algorithm together with
the meaning of its parameters. For every algorithm you are asked to (i) determine the correct initial
call, (ii) trace the algorithm on concrete inputs — often starting from a partial state in the middle of
the recursion — and (iii) give a mathematical specification of what the call computes as a function
of its parameters. One problem also asks you to fill in a missing line of pseudocode.
1. Backtracking specification: 3-Colorability
A proper 3-coloring of an undirected graph G = (V, E) on n vertices is a function f : V → {1, 2, 3}
assigning each vertex v a color f (v) such that the endpoints of every edge get different colors: for
each edge (u, v) ∈ E we have f (u) ̸= f (v). The 3-Colorability problem asks whether a given
graph admits a proper 3-coloring.
The algorithm below receives the adjacency matrix A[1 . . . n, 1 . . . n] of G (so A[i, j] = 1 iff (i, j) ∈ E,
and A[i, j] = 0 otherwise), an array C[1 . . . n] of colors, and an integer k.
Alg ThreeColor(Array A[1 . . . n, 1 . . . n], Array C[1 . . . n], int k)
if (k == n) then // all vertices colored: verify properness
for (i = 1 to n) do
for (j = 1 to n) do
if (A[i, j] == 1 and C[i] == C[j]) then return FALSE
return TRUE
else // assign a color to the next vertex
for (color = 1 to 3) do
C[k+1] = color
if (ThreeColor(A, C, k+1)) then return TRUE
C[k+1] = 0
return FALSE
(1a) [0.25 pt] What should the values of C[1 . . . n] and k be in the initial call, so that for an input
graph with adjacency matrix A the call ThreeColor(A, C, k) correctly determines whether G admits
a proper 3-coloring?
(1b) [0.25 pt] Consider the graph G1 on the right (edges {1-2, 2-3, 3-4, 4-1, 1-3}). What is the result
of running ThreeColor(A, C, k) with
C = [1, 2, 0, 0], k = 2?
1 2
If the algorithm returns a Boolean value, give that value. If it does not, state the
4 3
reason (endless loop? index-out-of-bounds?).
1
, (1c) [0.25 pt] Consider the complete graph K4 (vertices 1, 2, 3, 4, every pair adjacent). What is the
result of running ThreeColor(A, C, k) with
C = [1, 2, 3, 0], k = 3?
1 2
Same instructions as in (1b).
4 3
(1d) [0.75 pt] Give a mathematical statement that captures the output of ThreeColor in terms of
its parameters A, C, and k. It suffices to cover all inputs satisfying the preconditions:
A is the adjacency matrix of a graph G = (V, E) on n vertices;
C is an array of n integers with C[i] ∈ {1, 2, 3} for i ≤ k and C[i] = 0 for i > k;
k is an integer with 0 ≤ k ≤ n.
Your statement should capture how the partial coloring stored in C affects the output for the same
input graph A.
2. Backtracking specification: 0/1 Knapsack (maximum value)
In the 0/1 Knapsack problem we are given n items, where item i has a weight w[i] ≥ 0 and a value
v[i] ≥ 0, together with a capacity W ≥ 0. A selection is a subset of the items; it is feasible if its
total weight is at most W . The goal is the maximum total value of a feasible selection.
The algorithm receives arrays w[1 . . . n] and v[1 . . . n], the capacity W , an array S[1 . . . n] (where
S[i] = 1 means item i is selected and S[i] = 0 means it is not), and an integer k. We write −∞ to
mean “no feasible selection”.
Alg MaxValue(Array w[1 . . . n], Array v[1 . . . n], int W , Array S[1 . . . n], int k)
if (k == n) then // S is a complete selection: evaluate it
int weight = 0; int value = 0
for (i = 1 to n) do
if (S[i] == 1) then { weight = weight + w[i]; value = value + v[i] }
if (weight ≤ W ) then return value
else return −∞
else // decide whether item k+1 is taken
S[k+1] = 0
int best = MaxValue(w, v, W, S, k+1)
S[k+1] = 1
best = max(best, MaxValue(w, v, W, S, k+1))
S[k+1] = 0
return best
2
