Loading…

Worked solutions

IB Computer Science HL · Paper 3

Computer Science, Higher Level

Session: November 2021
Marks: 30
Duration: 1 hour
Calculator: Not allowed
Questions: 4

Keep your copy of the paper open alongside. We don't reproduce the questions: each part below is labelled to match the November 2021 Global paper, which your school or the IB can provide.

Practice mode

Hide our working until you've had a go.

Questions

Questions 1–4 · 30 marks

Question 1

4 marks

Core characteristics and elitism mechanisms in genetic algorithms

Modelling and simulation

(a)

2 marks

Identify two distinguishing characteristics of genetic algorithms:
1) Population-based evolutionary search: Operates concurrently on a diverse pool of potential solutions (chromosomes) rather than refining a single path, evolving new generations through biologically inspired operators like crossover and mutation.
2) Stochastic fitness-driven selection: Employs probabilistic sampling guided by an objective fitness function to favor high-performing solutions while preserving exploration across the search space.

Mentor tip

State two defining characteristics such as population-based evolutionary search or fitness-driven probabilistic selection.

(b)

2 marks

Outline the role and function of elitism in genetic algorithms:
Elitism guarantees that a predetermined number of the highest-fitness individuals from the current generation are copied directly into the subsequent generation without modification from crossover or mutation.
This mechanism preserves the best discovered solutions from being degraded or permanently lost due to destructive random genetic operations.

Mentor tip

Clarify that elitism copies top-scoring individuals unaltered into the next generation to safeguard the best solution found so far.

Question 2

8 marks

Cycle crossover (CX) execution and chromosome preservation in partially matched crossover (PMX)

Modelling and simulation

(a)

4 marks

Calculate the offspring from Parent 1 and Parent 2 using Cycle Crossover (CX):
Parent sequences:
$P1: [B, A, G, C, J, D, H, E, F, I]$
$P2: [D, C, I, E, B, G, A, H, J, F]$
Trace the cycle beginning at index 1 (1-indexed):
1) Start at index 1: P1 has B, P2 has D. Retain position 1: $City B$ .
2) Find where city D occurs in P1: D is located at index 6. At index 6, P2 has G. Retain position 6: $City D$ .
3) Find where city G occurs in P1: G is located at index 3. At index 3, P2 has I. Retain position 3: $City G$ .
4) Find where city I occurs in P1: I is located at index 10. At index 10, P2 has F. Retain position 10: $City I$ .
5) Find where city F occurs in P1: F is located at index 9. At index 9, P2 has J. Retain position 9: $City F$ .
6) Find where city J occurs in P1: J is located at index 5. At index 5, P2 has B. Retain position 5: $City J$ .
7) City B is the starting city, which completes Cycle 1 over indices: ${1, 3, 5, 6, 9, 10}$ .
Assemble Offspring 1 (copy Cycle 1 positions from P1, fill remaining indices ${2, 4, 7, 8}$ from P2):
$Indices 1, 3, 5, 6, 9, 10 from P1: [B,_, G,_, J, D,_,_, F, I]$
$Indices 2, 4, 7, 8 from P2: [_, C,_, E,_,_, A, H,_,_]$
Combining yields Offspring 1: $[B, C, G, E, J, D, A, H, F, I]$ .
Assemble Offspring 2 (copy Cycle 1 positions from P2, fill remaining indices from P1):
Combining yields Offspring 2: $[D, A, I, C, B, G, H, E, J, F]$ .

Cycle 1 Indices = {1, 3, 5, 6, 9, 10} Offspring 1 = [B, C, G, E, J, D, A, H, F, I] Offspring 2 = [D, A, I, C, B, G, H, E, J, F]

Mentor tip

Trace the cycle between matching positions in P1 and P2 until returning to the initial city, then fill non-cycle positions directly from the opposite parent.

(b)

4 marks

Outline how parental characteristics and valid permutation constraints are preserved during Partially Matched Crossover (PMX):
1) Random crossover segment selection: Two cut-points are chosen randomly along the parent chromosomes, defining an identical matching window across both parents.
2) Swapping and direct inheritance: For the first offspring, the selected central sub-sequence from Parent 1 is copied directly into the corresponding positions, preserving that contiguous sub-path intact.
3) Positional mapping relationships: A bidirectional mapping is constructed between each paired element within the crossover segment of Parent 1 and Parent 2.
4) Resolving duplicates outside the window: Elements from Parent 2 outside the cut-points are copied into the offspring; whenever a city already exists in the copied central window, the mapping is followed transitively to insert an unassigned city, preventing duplicate visits and preserving a valid tour.

Mentor tip

Explain the four stages: choosing crossover cut points, copying the sub-sequence, building the element mapping, and replacing duplicates using the mapping.

Question 3

6 marks

Comparative analysis of heuristic versus non-heuristic search methods in route optimization

Computational thinking, problem-solving and programming

6 marks

Compare and contrast the effectiveness of heuristic algorithms and non-heuristic algorithms for route optimization problems:
1) Guarantee of optimality versus computational speed: Non-heuristic exact algorithms (such as exhaustive brute-force search or integer linear programming) explore the complete solution space to guarantee discovering the globally optimal route. In contrast, heuristic algorithms (such as genetic algorithms or simulated annealing) prioritize polynomial execution time, trading away guaranteed mathematical optimality in exchange for practical, near-optimal approximations.
2) Computational tractability on large problem spaces: As the number of cities $n$ increases, the number of possible round-trip tours grows factorially according to $\frac{( n - 1 )!}{2}$ . For $n = 20$ cities, brute force requires evaluating over $6.08 \times 1 0^{16}$ paths, rendering non-heuristic exhaustive approaches computationally intractable. Heuristics remain practical because their computation scales polynomially with population size and generation limits.
3) Susceptibility to local optima: Simple non-heuristic greedy approaches like nearest-neighbor rapidly become trapped in local minima because they make irreversible myopic choices. Advanced meta-heuristics incorporate stochastic exploration (such as mutation and probabilistic parent selection) to break out of suboptimal local basins.
4) Contextual suitability: When lives or safety are at stake (such as designing mission-critical aircraft flight paths or surgical tool paths), non-heuristic exact methods may be mandatory regardless of computing cost. For practical commercial logistics, delivery dispatching, or recreational touring, heuristic methods provide satisfactory routes within minutes.

Total distinct symmetric tours = \frac{( n - 1 )!}{2}, \frac{19 !}{2} \approx 6.08 \times 1 0^{16}

Mentor tip

Structure the comparison across four key dimensions: optimality guarantees, factorial vs polynomial time complexity, escape from local minima, and practical domain trade-offs.

Question 4

12 marks

Hyperparameter configuration and stopping criteria for genetic algorithms

Modelling and simulation

12 marks

Discuss how initial variable configurations and stopping criteria influence the performance and success of Fenna's genetic algorithm for the travelling salesman problem:
Impact of population size configuration:
- Excessively small population: If the population contains too few routes (e.g., fewer than 20), genetic diversity remains severely restricted. High-fitness chromosomes dominate the pool within a few iterations, causing premature convergence on a poor local minimum.
- Excessively large population: While large populations (e.g., hundreds or thousands of routes) provide broad coverage of the search space, computing the fitness function across every individual in every generation causes high CPU overhead and slows convergence time significantly.
- Optimal balance: A moderate population size (e.g., 50 to 100 individuals) combined with mild elitism balances genetic diversity with rapid generation throughput.
Impact of initial population route generation strategy:
- Completely random initialization: Generating initial tours entirely at random ensures uniform sampling across the search space, but introduces many low-quality, self-intersecting routes that require many generations to filter out.
- Seeding with heuristic approximations: Initializing a subset of the population using fast greedy heuristics (e.g., nearest neighbor) or human-drawn reasonable tours provides high-quality baseline building blocks, accelerating convergence. However, the remainder of the population must remain random to preserve overall genetic variety and avoid immediate local bias.
Impact of mutation rate tuning:
- Low mutation rate: A mutation rate near 0% restricts the algorithm to recombining existing traits. When parents share similar sequences, crossover cannot create new permutations, causing early stagnation.
- High mutation rate: If mutation exceeds 5% to 10%, beneficial route segments are continually disrupted, causing the algorithm to degenerate into an inefficient random walk that struggles to fine-tune good solutions.
- Standard setting: A modest mutation rate of approximately 1% to 2% provides sufficient disruption to escape local minima while allowing crossover to exploit discovered high-fitness building blocks.
Impact of stopping criteria selection:
- Fixed generation or runtime limit: Halting after a fixed threshold (e.g., 500 generations or 60 seconds) guarantees predictable execution time, which suits time-sensitive applications. However, if the threshold is set too low, the algorithm terminates before finding a near-optimal solution; if set too high, compute is wasted after convergence.
- Fitness plateau stagnation limit: Halting when the best route fitness fails to improve for a consecutive number of generations (e.g., no change over 50 generations) ensures the algorithm stops promptly once convergence occurs without wasting processor cycles.
- Target threshold limit: Terminating once route distance falls below a predetermined distance benchmark guarantees satisfactory path quality, though setting an unrealistic target may result in infinite execution.
Synthesis and recommendation:
Fenna should initialize a balanced population of approximately 50 to 100 routes, seeded with 10% greedy nearest-neighbor paths and 90% random routes. She should pair roulette wheel selection with a 1% swap-mutation rate and an elitism count of 2. For stopping criteria, she should combine a hard timeout limit with a stagnation threshold of 50 generations without fitness improvement, ensuring robust convergence within Lotte's departure timeline.

Mentor tip

Examine all four assigned decisions: population size, initial routes, mutation rate, and stopping criteria, evaluating their direct trade-offs between exploration and exploitation.

Our analysis

Where the marks are

Each part sorted by the topic it mostly tests. Modelling and simulation carries the most marks on this paper.

Modelling and simulation24 marks · 80%
Q1, Q2, Q4
Computational thinking, problem-solving and programming6 marks · 20%
Q3

Mentor insights

Traps to watch for

01
Confusing elitism with pure truncation selection · Q1
Elitism copies the top one or two individuals directly into the next generation to prevent loss of the best solution, whereas truncation replaces the entire mating pool with only the top fraction of prospective solutions.
02
Skipping element mapping when generating PMX offspring · Q2
In PMX, non-window elements cannot be copied blindly from the other parent; duplicate cities must be translated via the bidirectional window mapping to maintain a valid tour.
03
Relying on a single stopping condition without a stagnation check · Q4
A fixed generation limit either terminates prematurely or wastes computation after convergence; combining a maximum generation cap with a stagnation threshold yields the most reliable termination.

Solutions and tips are GeorgeTheTutor's own; the questions are not reproduced here. Not affiliated with or endorsed by the International Baccalaureate Organization.

Want someone to go through your paper with you?

Our maths mentors took these exams recently. One-to-one, they'll find where your marks are going and fix it before May.

Find your maths mentor More past papers

Worked solutions

IB Computer Science HL · Paper 3

Computer Science, Higher Level

Session: November 2021
Marks: 30
Duration: 1 hour
Calculator: Not allowed
Questions: 4

Q1 Q2 Q3 Q4

Keep your copy of the paper open alongside. We don't reproduce the questions: each part below is labelled to match the November 2021 Global paper, which your school or the IB can provide.

Practice mode

Hide our working until you've had a go.

Questions

Questions 1–4 · 30 marks

Question 1

4 marks

Core characteristics and elitism mechanisms in genetic algorithms

Modelling and simulation

(a)

2 marks

Identify two distinguishing characteristics of genetic algorithms:
1) Population-based evolutionary search: Operates concurrently on a diverse pool of potential solutions (chromosomes) rather than refining a single path, evolving new generations through biologically inspired operators like crossover and mutation.
2) Stochastic fitness-driven selection: Employs probabilistic sampling guided by an objective fitness function to favor high-performing solutions while preserving exploration across the search space.

Mentor tip

State two defining characteristics such as population-based evolutionary search or fitness-driven probabilistic selection.

(b)

2 marks

Outline the role and function of elitism in genetic algorithms:
Elitism guarantees that a predetermined number of the highest-fitness individuals from the current generation are copied directly into the subsequent generation without modification from crossover or mutation.
This mechanism preserves the best discovered solutions from being degraded or permanently lost due to destructive random genetic operations.

Mentor tip

Clarify that elitism copies top-scoring individuals unaltered into the next generation to safeguard the best solution found so far.

Question 2

8 marks

Cycle crossover (CX) execution and chromosome preservation in partially matched crossover (PMX)

Modelling and simulation

(a)

4 marks

Calculate the offspring from Parent 1 and Parent 2 using Cycle Crossover (CX):
Parent sequences:
$P1: [B, A, G, C, J, D, H, E, F, I]$
$P2: [D, C, I, E, B, G, A, H, J, F]$
Trace the cycle beginning at index 1 (1-indexed):
1) Start at index 1: P1 has B, P2 has D. Retain position 1: $City B$ .
2) Find where city D occurs in P1: D is located at index 6. At index 6, P2 has G. Retain position 6: $City D$ .
3) Find where city G occurs in P1: G is located at index 3. At index 3, P2 has I. Retain position 3: $City G$ .
4) Find where city I occurs in P1: I is located at index 10. At index 10, P2 has F. Retain position 10: $City I$ .
5) Find where city F occurs in P1: F is located at index 9. At index 9, P2 has J. Retain position 9: $City F$ .
6) Find where city J occurs in P1: J is located at index 5. At index 5, P2 has B. Retain position 5: $City J$ .
7) City B is the starting city, which completes Cycle 1 over indices: ${1, 3, 5, 6, 9, 10}$ .
Assemble Offspring 1 (copy Cycle 1 positions from P1, fill remaining indices ${2, 4, 7, 8}$ from P2):
$Indices 1, 3, 5, 6, 9, 10 from P1: [B,_, G,_, J, D,_,_, F, I]$
$Indices 2, 4, 7, 8 from P2: [_, C,_, E,_,_, A, H,_,_]$
Combining yields Offspring 1: $[B, C, G, E, J, D, A, H, F, I]$ .
Assemble Offspring 2 (copy Cycle 1 positions from P2, fill remaining indices from P1):
Combining yields Offspring 2: $[D, A, I, C, B, G, H, E, J, F]$ .

Cycle 1 Indices = {1, 3, 5, 6, 9, 10} Offspring 1 = [B, C, G, E, J, D, A, H, F, I] Offspring 2 = [D, A, I, C, B, G, H, E, J, F]

Mentor tip

Trace the cycle between matching positions in P1 and P2 until returning to the initial city, then fill non-cycle positions directly from the opposite parent.

(b)

4 marks

Outline how parental characteristics and valid permutation constraints are preserved during Partially Matched Crossover (PMX):
1) Random crossover segment selection: Two cut-points are chosen randomly along the parent chromosomes, defining an identical matching window across both parents.
2) Swapping and direct inheritance: For the first offspring, the selected central sub-sequence from Parent 1 is copied directly into the corresponding positions, preserving that contiguous sub-path intact.
3) Positional mapping relationships: A bidirectional mapping is constructed between each paired element within the crossover segment of Parent 1 and Parent 2.
4) Resolving duplicates outside the window: Elements from Parent 2 outside the cut-points are copied into the offspring; whenever a city already exists in the copied central window, the mapping is followed transitively to insert an unassigned city, preventing duplicate visits and preserving a valid tour.

Mentor tip

Explain the four stages: choosing crossover cut points, copying the sub-sequence, building the element mapping, and replacing duplicates using the mapping.

Question 3

6 marks

Comparative analysis of heuristic versus non-heuristic search methods in route optimization

Computational thinking, problem-solving and programming

6 marks

Compare and contrast the effectiveness of heuristic algorithms and non-heuristic algorithms for route optimization problems:
1) Guarantee of optimality versus computational speed: Non-heuristic exact algorithms (such as exhaustive brute-force search or integer linear programming) explore the complete solution space to guarantee discovering the globally optimal route. In contrast, heuristic algorithms (such as genetic algorithms or simulated annealing) prioritize polynomial execution time, trading away guaranteed mathematical optimality in exchange for practical, near-optimal approximations.
2) Computational tractability on large problem spaces: As the number of cities $n$ increases, the number of possible round-trip tours grows factorially according to $\frac{( n - 1 )!}{2}$ . For $n = 20$ cities, brute force requires evaluating over $6.08 \times 1 0^{16}$ paths, rendering non-heuristic exhaustive approaches computationally intractable. Heuristics remain practical because their computation scales polynomially with population size and generation limits.
3) Susceptibility to local optima: Simple non-heuristic greedy approaches like nearest-neighbor rapidly become trapped in local minima because they make irreversible myopic choices. Advanced meta-heuristics incorporate stochastic exploration (such as mutation and probabilistic parent selection) to break out of suboptimal local basins.
4) Contextual suitability: When lives or safety are at stake (such as designing mission-critical aircraft flight paths or surgical tool paths), non-heuristic exact methods may be mandatory regardless of computing cost. For practical commercial logistics, delivery dispatching, or recreational touring, heuristic methods provide satisfactory routes within minutes.

Total distinct symmetric tours = \frac{( n - 1 )!}{2}, \frac{19 !}{2} \approx 6.08 \times 1 0^{16}

Mentor tip

Structure the comparison across four key dimensions: optimality guarantees, factorial vs polynomial time complexity, escape from local minima, and practical domain trade-offs.

Question 4

12 marks

Hyperparameter configuration and stopping criteria for genetic algorithms

Modelling and simulation

12 marks

Discuss how initial variable configurations and stopping criteria influence the performance and success of Fenna's genetic algorithm for the travelling salesman problem:
Impact of population size configuration:
- Excessively small population: If the population contains too few routes (e.g., fewer than 20), genetic diversity remains severely restricted. High-fitness chromosomes dominate the pool within a few iterations, causing premature convergence on a poor local minimum.
- Excessively large population: While large populations (e.g., hundreds or thousands of routes) provide broad coverage of the search space, computing the fitness function across every individual in every generation causes high CPU overhead and slows convergence time significantly.
- Optimal balance: A moderate population size (e.g., 50 to 100 individuals) combined with mild elitism balances genetic diversity with rapid generation throughput.
Impact of initial population route generation strategy:
- Completely random initialization: Generating initial tours entirely at random ensures uniform sampling across the search space, but introduces many low-quality, self-intersecting routes that require many generations to filter out.
- Seeding with heuristic approximations: Initializing a subset of the population using fast greedy heuristics (e.g., nearest neighbor) or human-drawn reasonable tours provides high-quality baseline building blocks, accelerating convergence. However, the remainder of the population must remain random to preserve overall genetic variety and avoid immediate local bias.
Impact of mutation rate tuning:
- Low mutation rate: A mutation rate near 0% restricts the algorithm to recombining existing traits. When parents share similar sequences, crossover cannot create new permutations, causing early stagnation.
- High mutation rate: If mutation exceeds 5% to 10%, beneficial route segments are continually disrupted, causing the algorithm to degenerate into an inefficient random walk that struggles to fine-tune good solutions.
- Standard setting: A modest mutation rate of approximately 1% to 2% provides sufficient disruption to escape local minima while allowing crossover to exploit discovered high-fitness building blocks.
Impact of stopping criteria selection:
- Fixed generation or runtime limit: Halting after a fixed threshold (e.g., 500 generations or 60 seconds) guarantees predictable execution time, which suits time-sensitive applications. However, if the threshold is set too low, the algorithm terminates before finding a near-optimal solution; if set too high, compute is wasted after convergence.
- Fitness plateau stagnation limit: Halting when the best route fitness fails to improve for a consecutive number of generations (e.g., no change over 50 generations) ensures the algorithm stops promptly once convergence occurs without wasting processor cycles.
- Target threshold limit: Terminating once route distance falls below a predetermined distance benchmark guarantees satisfactory path quality, though setting an unrealistic target may result in infinite execution.
Synthesis and recommendation:
Fenna should initialize a balanced population of approximately 50 to 100 routes, seeded with 10% greedy nearest-neighbor paths and 90% random routes. She should pair roulette wheel selection with a 1% swap-mutation rate and an elitism count of 2. For stopping criteria, she should combine a hard timeout limit with a stagnation threshold of 50 generations without fitness improvement, ensuring robust convergence within Lotte's departure timeline.

Mentor tip

Examine all four assigned decisions: population size, initial routes, mutation rate, and stopping criteria, evaluating their direct trade-offs between exploration and exploitation.

Our analysis

Where the marks are

Each part sorted by the topic it mostly tests. Modelling and simulation carries the most marks on this paper.

Modelling and simulation24 marks · 80%
Q1, Q2, Q4
Computational thinking, problem-solving and programming6 marks · 20%
Q3

Mentor insights

Traps to watch for

01
Confusing elitism with pure truncation selection · Q1
Elitism copies the top one or two individuals directly into the next generation to prevent loss of the best solution, whereas truncation replaces the entire mating pool with only the top fraction of prospective solutions.
02
Skipping element mapping when generating PMX offspring · Q2
In PMX, non-window elements cannot be copied blindly from the other parent; duplicate cities must be translated via the bidirectional window mapping to maintain a valid tour.
03
Relying on a single stopping condition without a stagnation check · Q4
A fixed generation limit either terminates prematurely or wastes computation after convergence; combining a maximum generation cap with a stagnation threshold yields the most reliable termination.

Solutions and tips are GeorgeTheTutor's own; the questions are not reproduced here. Not affiliated with or endorsed by the International Baccalaureate Organization.

Want someone to go through your paper with you?

Our maths mentors took these exams recently. One-to-one, they'll find where your marks are going and fix it before May.

Find your maths mentor More past papers