Loading…

Worked solutions

IB Computer Science HL · Paper 3

Computer Science, Higher Level

Session: May 2022
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 May 2022 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

Heuristic problem-solving principles and causes of premature convergence

Modelling and simulation

(a)

2 marks

Outline the core principles of a heuristic algorithm in computational optimization:
A heuristic algorithm is an educated search strategy designed to discover an approximate, satisfactory solution to computationally hard or NP-intractable problems within a reasonable timeframe.
It deliberately trades guaranteed mathematical optimality for computational efficiency, avoiding prohibitive factorial execution times in large combinatorial search spaces.

Mentor tip

State that a heuristic produces practical approximate solutions within realistic timeframes where exhaustive exact algorithms are computationally intractable.

(b)

2 marks

Identify two primary causes of premature convergence in genetic algorithms:
1) Inadequate initial population diversity: Initializing the search with too small a population or with overly homogeneous routes limits the genetic building blocks, causing the population to cluster around a suboptimal local minimum early in the search.
2) Overly aggressive selection pressure or negligible mutation: When top-performing routes disproportionately dominate the mating pool without sufficient random mutation, variety is quickly eliminated before alternative regions of the search space can be explored.

Mentor tip

Identify insufficient initial population size and low mutation rates or excessive selection pressure as key drivers of premature convergence.

Question 2

8 marks

Order crossover (OX) walkthrough and parameter interactions in genetic optimization

Modelling and simulation

(a)

4 marks

Calculate the offspring tour from Parent 1 and Parent 2 using the Order Crossover (OX) method:
Given parents with 10 cities ( $A$ through $J$ ):
$Parent 1: [B, G, H, D, E, C, J, F, I, A]$
$Parent 2: [A, E, I, D, G, F, J, C, H, B]$
The preserved central sub-sequence from Parent 1 is $H, D, E, C, J$ occupying positions 3 through 7:
$Offspring stage 1: [_,_, H, D, E, C, J,_,_,_]$
List Parent 2 starting immediately after the cut point (position 7), wrapping cyclically around to the start:
$Order from Parent 2: C, H, B, A, E, I, D, G, F, J$
Filter out all cities already present in the preserved sub-sequence ${H, D, E, C, J}$ :
- $C$ : already present (skip)
- $H$ : already present (skip)
- $B$ : unassigned (insert at position 8)
$Offspring stage 2: [_,_, H, D, E, C, J, B,_,_]$
- $A$ : unassigned (insert at position 9)
$Offspring stage 3: [_,_, H, D, E, C, J, B, A,_]$
- $E$ : already present (skip)
- $I$ : unassigned (insert at position 10)
$Offspring stage 4: [_,_, H, D, E, C, J, B, A, I]$
- $D$ : already present (skip)
- $G$ : unassigned (wrap around, insert at position 1)
$Offspring stage 5: [G,_, H, D, E, C, J, B, A, I]$
- $F$ : unassigned (insert at position 2)
$Final Offspring: [G, F, H, D, E, C, J, B, A, I]$

Parent 1 Sub-sequence = [H, D, E, C, J] Parent 2 Filtered Sequence = [B, A, I, G, F] Completed Offspring = [G, F, H, D, E, C, J, B, A, I]

Mentor tip

Read Parent 2 cyclically starting right after the second cut point, skip cities already placed in the sub-sequence, and fill empty slots sequentially wrapping back to position 1.

(b)

4 marks

Explain how population size and mutation rate affect the probability of discovering an optimal solution:
1) Influence of population size: A larger population contains a wider variety of genetic traits, allowing simultaneous parallel sampling across disparate regions of the route space and lowering the risk of becoming trapped in local minima; however, very large populations incur heavy per-generation computational overhead.
2) Influence of mutation rate: A well-calibrated mutation rate introduces novel route variations that cannot be produced by crossover alone, providing the necessary perturbation to break out of local stagnation; however, setting the mutation rate too high destroys beneficial sub-tours, turning the evolutionary search into an unproductive random walk.
3) Parameter interaction: Achieving a near-optimal solution depends on balancing exploration and exploitation. A moderately sized population paired with a small mutation rate (e.g., 1% to 2%) preserves promising sub-paths while sustaining enough diversity to discover the global optimum.

Mentor tip

Explain the trade-offs of both variables: population size governing diversity versus calculation runtime, and mutation rate enabling local-minimum escape without destroying fit sub-tours.

Question 3

6 marks

Comparative evaluation of roulette wheel versus truncation selection

Modelling and simulation

6 marks

Compare and contrast roulette wheel selection and truncation selection methods in genetic algorithms:
1) Selection mechanism and probability distribution: In roulette wheel selection, each route is assigned a selection probability strictly proportional to its relative fitness; every individual in the population maintains a non-zero probability of being selected. In truncation selection, routes are sorted by fitness, and only a predetermined top proportion (e.g., top $N$ percent) are retained in the mating pool, with all below-threshold routes permanently discarded.
2) Within-pool differentiation: Within the truncation pool, all retained individuals share an identical probability of being chosen for breeding, irrespective of whether an individual ranked first or $N$ -th. Conversely, roulette wheel selection continuously differentiates individuals according to their fitness scores.
3) Preservation of genetic diversity: Roulette wheel selection preserves greater diversity because even low-fitness routes have a stochastic chance of contributing unique city links to the next generation, reducing premature convergence. Truncation selection exerts heavy selection pressure that accelerates convergence speed, but risks premature stagnation if the top tier converges early.
4) Computational complexity: Roulette wheel selection requires computing fitness across the entire population and generating cumulative probability slices. Truncation requires sorting the population by fitness, but sampling from the top slice is computationally simple and predictable.
5) Strategic combination: In practical route planning, practitioners often start with truncation selection to eliminate poor random routes quickly, then switch to roulette wheel selection or tournament selection to maintain genetic variation during later generations.

P_{i} = \frac{f _{i}}{\sum _{j = 1}^{N} f _{j}} (Roulette Wheel), P_{i} = {\frac{1}{K} 0 if rank (i) \leq K if rank (i) > K (Truncation)

Mentor tip

Address selection mechanics, within-pool probability distributions, impact on genetic diversity and premature convergence, and computational overhead for both methods.

Question 4

12 marks

Comprehensive evaluation of genetic algorithms for combinatorial route optimization

Modelling and simulation

12 marks

Evaluate the extent to which the characteristics of genetic algorithms make them an appropriate approach for solving the travelling salesman problem in motorcycle touring:
Scale of the problem space and computational intractability:
- Combinatorial explosion: Visiting 20 designated cities before returning to the start creates a factorial search space of $\frac{( 20 - 1 )!}{2} = \frac{19 !}{2} \approx 6.08 \times 1 0^{16}$ distinct valid round-trip tours. Evaluating every permutation by brute force on a domestic computer would require centuries, rendering non-heuristic exhaustive algorithms impossible for Lotte's weekend deadline.
- Role of heuristic search: Genetic algorithms operate as population-based stochastic heuristics that sample promising permutations concurrently, producing high-quality, near-optimal tours within minutes or hours.
Characteristics supporting genetic algorithm suitability:
- Parallel exploration of the search space: Maintaining a population of diverse routes allows simultaneous exploration across multiple geographic corridors rather than following a single trajectory.
- Specialized permutation operators: Order crossover (OX), cycle crossover (CX), and partially matched crossover (PMX) preserve contiguous sequences of well-connected cities while ensuring that no city is visited twice or omitted.
- Controllable exploration-exploitation trade-off: Combining fitness-proportionate selection with small mutation rates allows the algorithm to exploit discovered short segments while retaining the ability to jump out of local minima.
- Practical stopping criteria: The algorithm can be configured to stop after a set runtime or generation count, guaranteeing that Lotte receives a usable route before her scheduled Monday departure.
Limitations and challenges of genetic algorithms in route planning:
- No guarantee of the global optimum: Genetic algorithms find near-optimal approximations; there is no mathematical proof that the output represents the absolute shortest possible distance.
- Sensitivity to hyperparameter tuning: Convergence quality depends heavily on selecting appropriate population sizes, mutation rates, and selection operators; poor tuning can cause premature convergence or unproductive random searches.
- Exclusive focus on quantitative distance: Genetic algorithms optimize purely against the distance matrix. Real-world touring involves critical qualitative considerations that the distance table ignores, including scenic quality, road surfaces, elevation changes, traffic congestion, and fuel station availability.
- Inability to explain decisions: Unlike rule-based systems, genetic algorithms do not provide transparent logical explanations for why specific detours or sequences were chosen.
Strategic conclusion and recommendation:
Genetic algorithms are exceptionally well-suited for solving the mathematical core of the travelling salesman problem under strict time constraints, converting an otherwise intractable $1 0^{16}$ route space into a viable touring plan. However, because the algorithm optimizes solely for numeric distance, Lotte should use the genetic algorithm to generate the top three shortest potential itineraries, and then manually review them against local maps, scenic preferences, and road conditions before finalizing her motorcycle route.

Search space = \frac{( 20 - 1 )!}{2} = \frac{19 !}{2} \approx 6.08 \times 1 0^{16} routes

Mentor tip

Ground the discussion in the mathematical scale of the 20-city problem ( $1 0^{16}$ routes), contrast parallel GA exploration with brute-force intractability, note real-world qualitative road constraints, and provide a balanced conclusion.

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 simulation30 marks · 100%
Q1, Q2, Q3, Q4

Mentor insights

Traps to watch for

01
Confusing premature convergence with reaching the global optimum · Q1
Premature convergence occurs when the population loses diversity and gets stuck on a suboptimal local minimum early, not when the global shortest tour has been found.
02
Reading Parent 2 from the start instead of cyclically after the second cut point in OX · Q2
In Order Crossover (OX), Parent 2 must be traversed cyclically starting immediately after the second cut point, wrapping to the start, not read from index 1.
03
Treating quantitative distance minimization as the only criterion for route suitability · Q4
A pure genetic algorithm minimizes kilometer distances, but motorcycle touring depends heavily on qualitative factors like road conditions, weather, and scenic quality that the distance matrix ignores.

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: May 2022
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 May 2022 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

Heuristic problem-solving principles and causes of premature convergence

Modelling and simulation

(a)

2 marks

Outline the core principles of a heuristic algorithm in computational optimization:
A heuristic algorithm is an educated search strategy designed to discover an approximate, satisfactory solution to computationally hard or NP-intractable problems within a reasonable timeframe.
It deliberately trades guaranteed mathematical optimality for computational efficiency, avoiding prohibitive factorial execution times in large combinatorial search spaces.

Mentor tip

State that a heuristic produces practical approximate solutions within realistic timeframes where exhaustive exact algorithms are computationally intractable.

(b)

2 marks

Identify two primary causes of premature convergence in genetic algorithms:
1) Inadequate initial population diversity: Initializing the search with too small a population or with overly homogeneous routes limits the genetic building blocks, causing the population to cluster around a suboptimal local minimum early in the search.
2) Overly aggressive selection pressure or negligible mutation: When top-performing routes disproportionately dominate the mating pool without sufficient random mutation, variety is quickly eliminated before alternative regions of the search space can be explored.

Mentor tip

Identify insufficient initial population size and low mutation rates or excessive selection pressure as key drivers of premature convergence.

Question 2

8 marks

Order crossover (OX) walkthrough and parameter interactions in genetic optimization

Modelling and simulation

(a)

4 marks

Calculate the offspring tour from Parent 1 and Parent 2 using the Order Crossover (OX) method:
Given parents with 10 cities ( $A$ through $J$ ):
$Parent 1: [B, G, H, D, E, C, J, F, I, A]$
$Parent 2: [A, E, I, D, G, F, J, C, H, B]$
The preserved central sub-sequence from Parent 1 is $H, D, E, C, J$ occupying positions 3 through 7:
$Offspring stage 1: [_,_, H, D, E, C, J,_,_,_]$
List Parent 2 starting immediately after the cut point (position 7), wrapping cyclically around to the start:
$Order from Parent 2: C, H, B, A, E, I, D, G, F, J$
Filter out all cities already present in the preserved sub-sequence ${H, D, E, C, J}$ :
- $C$ : already present (skip)
- $H$ : already present (skip)
- $B$ : unassigned (insert at position 8)
$Offspring stage 2: [_,_, H, D, E, C, J, B,_,_]$
- $A$ : unassigned (insert at position 9)
$Offspring stage 3: [_,_, H, D, E, C, J, B, A,_]$
- $E$ : already present (skip)
- $I$ : unassigned (insert at position 10)
$Offspring stage 4: [_,_, H, D, E, C, J, B, A, I]$
- $D$ : already present (skip)
- $G$ : unassigned (wrap around, insert at position 1)
$Offspring stage 5: [G,_, H, D, E, C, J, B, A, I]$
- $F$ : unassigned (insert at position 2)
$Final Offspring: [G, F, H, D, E, C, J, B, A, I]$

Parent 1 Sub-sequence = [H, D, E, C, J] Parent 2 Filtered Sequence = [B, A, I, G, F] Completed Offspring = [G, F, H, D, E, C, J, B, A, I]

Mentor tip

Read Parent 2 cyclically starting right after the second cut point, skip cities already placed in the sub-sequence, and fill empty slots sequentially wrapping back to position 1.

(b)

4 marks

Explain how population size and mutation rate affect the probability of discovering an optimal solution:
1) Influence of population size: A larger population contains a wider variety of genetic traits, allowing simultaneous parallel sampling across disparate regions of the route space and lowering the risk of becoming trapped in local minima; however, very large populations incur heavy per-generation computational overhead.
2) Influence of mutation rate: A well-calibrated mutation rate introduces novel route variations that cannot be produced by crossover alone, providing the necessary perturbation to break out of local stagnation; however, setting the mutation rate too high destroys beneficial sub-tours, turning the evolutionary search into an unproductive random walk.
3) Parameter interaction: Achieving a near-optimal solution depends on balancing exploration and exploitation. A moderately sized population paired with a small mutation rate (e.g., 1% to 2%) preserves promising sub-paths while sustaining enough diversity to discover the global optimum.

Mentor tip

Explain the trade-offs of both variables: population size governing diversity versus calculation runtime, and mutation rate enabling local-minimum escape without destroying fit sub-tours.

Question 3

6 marks

Comparative evaluation of roulette wheel versus truncation selection

Modelling and simulation

6 marks

Compare and contrast roulette wheel selection and truncation selection methods in genetic algorithms:
1) Selection mechanism and probability distribution: In roulette wheel selection, each route is assigned a selection probability strictly proportional to its relative fitness; every individual in the population maintains a non-zero probability of being selected. In truncation selection, routes are sorted by fitness, and only a predetermined top proportion (e.g., top $N$ percent) are retained in the mating pool, with all below-threshold routes permanently discarded.
2) Within-pool differentiation: Within the truncation pool, all retained individuals share an identical probability of being chosen for breeding, irrespective of whether an individual ranked first or $N$ -th. Conversely, roulette wheel selection continuously differentiates individuals according to their fitness scores.
3) Preservation of genetic diversity: Roulette wheel selection preserves greater diversity because even low-fitness routes have a stochastic chance of contributing unique city links to the next generation, reducing premature convergence. Truncation selection exerts heavy selection pressure that accelerates convergence speed, but risks premature stagnation if the top tier converges early.
4) Computational complexity: Roulette wheel selection requires computing fitness across the entire population and generating cumulative probability slices. Truncation requires sorting the population by fitness, but sampling from the top slice is computationally simple and predictable.
5) Strategic combination: In practical route planning, practitioners often start with truncation selection to eliminate poor random routes quickly, then switch to roulette wheel selection or tournament selection to maintain genetic variation during later generations.

P_{i} = \frac{f _{i}}{\sum _{j = 1}^{N} f _{j}} (Roulette Wheel), P_{i} = {\frac{1}{K} 0 if rank (i) \leq K if rank (i) > K (Truncation)

Mentor tip

Address selection mechanics, within-pool probability distributions, impact on genetic diversity and premature convergence, and computational overhead for both methods.

Question 4

12 marks

Comprehensive evaluation of genetic algorithms for combinatorial route optimization

Modelling and simulation

12 marks

Evaluate the extent to which the characteristics of genetic algorithms make them an appropriate approach for solving the travelling salesman problem in motorcycle touring:
Scale of the problem space and computational intractability:
- Combinatorial explosion: Visiting 20 designated cities before returning to the start creates a factorial search space of $\frac{( 20 - 1 )!}{2} = \frac{19 !}{2} \approx 6.08 \times 1 0^{16}$ distinct valid round-trip tours. Evaluating every permutation by brute force on a domestic computer would require centuries, rendering non-heuristic exhaustive algorithms impossible for Lotte's weekend deadline.
- Role of heuristic search: Genetic algorithms operate as population-based stochastic heuristics that sample promising permutations concurrently, producing high-quality, near-optimal tours within minutes or hours.
Characteristics supporting genetic algorithm suitability:
- Parallel exploration of the search space: Maintaining a population of diverse routes allows simultaneous exploration across multiple geographic corridors rather than following a single trajectory.
- Specialized permutation operators: Order crossover (OX), cycle crossover (CX), and partially matched crossover (PMX) preserve contiguous sequences of well-connected cities while ensuring that no city is visited twice or omitted.
- Controllable exploration-exploitation trade-off: Combining fitness-proportionate selection with small mutation rates allows the algorithm to exploit discovered short segments while retaining the ability to jump out of local minima.
- Practical stopping criteria: The algorithm can be configured to stop after a set runtime or generation count, guaranteeing that Lotte receives a usable route before her scheduled Monday departure.
Limitations and challenges of genetic algorithms in route planning:
- No guarantee of the global optimum: Genetic algorithms find near-optimal approximations; there is no mathematical proof that the output represents the absolute shortest possible distance.
- Sensitivity to hyperparameter tuning: Convergence quality depends heavily on selecting appropriate population sizes, mutation rates, and selection operators; poor tuning can cause premature convergence or unproductive random searches.
- Exclusive focus on quantitative distance: Genetic algorithms optimize purely against the distance matrix. Real-world touring involves critical qualitative considerations that the distance table ignores, including scenic quality, road surfaces, elevation changes, traffic congestion, and fuel station availability.
- Inability to explain decisions: Unlike rule-based systems, genetic algorithms do not provide transparent logical explanations for why specific detours or sequences were chosen.
Strategic conclusion and recommendation:
Genetic algorithms are exceptionally well-suited for solving the mathematical core of the travelling salesman problem under strict time constraints, converting an otherwise intractable $1 0^{16}$ route space into a viable touring plan. However, because the algorithm optimizes solely for numeric distance, Lotte should use the genetic algorithm to generate the top three shortest potential itineraries, and then manually review them against local maps, scenic preferences, and road conditions before finalizing her motorcycle route.

Search space = \frac{( 20 - 1 )!}{2} = \frac{19 !}{2} \approx 6.08 \times 1 0^{16} routes

Mentor tip

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 simulation30 marks · 100%
Q1, Q2, Q3, Q4

Mentor insights

Traps to watch for

01
Confusing premature convergence with reaching the global optimum · Q1
Premature convergence occurs when the population loses diversity and gets stuck on a suboptimal local minimum early, not when the global shortest tour has been found.
02
Reading Parent 2 from the start instead of cyclically after the second cut point in OX · Q2
In Order Crossover (OX), Parent 2 must be traversed cyclically starting immediately after the second cut point, wrapping to the start, not read from index 1.
03
Treating quantitative distance minimization as the only criterion for route suitability · Q4
A pure genetic algorithm minimizes kilometer distances, but motorcycle touring depends heavily on qualitative factors like road conditions, weather, and scenic quality that the distance matrix ignores.

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