Loading…

Worked solutions

IB Computer Science HL · Paper 3

Computer Science, Higher Level

Session: November 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 November 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

Combinatorial optimization principles and local optimum traps in hill climbing

Modelling and simulation

(a)

2 marks

Outline why combinatorial optimization is applied to the travelling salesman problem:
The travelling salesman problem requires discovering the shortest or near-optimal closed tour from a finite, discrete set of permutations of cities.
Because total possible tour permutations grow factorially according to $\frac{( n - 1 )!}{2}$ , exhaustive brute-force search becomes computationally intractable, requiring combinatorial optimization techniques to prune the vast search space and reach feasible solutions quickly.

Permutations = \frac{( n - 1 )!}{2}

Mentor tip

State that combinatorial optimization finds near-optimal tours across discrete permutation sets where exhaustive factorial searches are intractable.

(b)

2 marks

Outline one significant drawback of using simple hill climbing for route optimization:
Susceptibility to local optima: Standard hill climbing only inspects immediate neighboring routes and halts whenever all adjacent single-swap modifications yield inferior tour distances.
Because the algorithm lacks stochastic mechanisms to tolerate temporarily worse solutions or leap across fitness barriers, it becomes permanently trapped on suboptimal local peaks rather than reaching the global optimum.

Mentor tip

Explain that hill climbing halts at the first local optimum because it only tests adjacent neighbors and cannot tolerate worse moves to escape.

Question 2

8 marks

Algorithmic versus manual cycling route design and role of mutation in similar parent tours

System fundamentals
Modelling and simulation

(a)

4 marks

Compare and contrast utilizing a genetic algorithm versus human race organizers for planning a 20-city annual cycling race route:
1) Optimization objective and speed: A genetic algorithm processes millions of distance combinations rapidly and objectively to minimize mathematical route length. Human organizers require days or weeks to draft routes manually and are prone to calculation errors.
2) Qualitative and holistic constraints: Human organizers incorporate real-world safety considerations, road surface quality, elevation gradients, scenic tourist landmarks, spectator viewing accessibility, and municipal traffic disruption. A basic genetic algorithm only optimizes the numerical distance matrix, ignoring qualitative infrastructure factors unless complex penalty functions are programmed.
3) Fairness and neutrality: Algorithmic planning eliminates human bias or favoritism toward specific competitors or teams, whereas human organizers might unconsciously design stages that favor local sprinters or climbers.
4) Social and community disruption: Organizers consult with local city councils and emergency services regarding road closures and local holidays. An unconstrained genetic algorithm might generate impractical routes that isolate hospitals or sever major transport arteries.

Mentor tip

Contrast computational speed and objective distance minimization against vital qualitative factors such as rider safety, road conditions, spectator engagement, and civic logistics.

(b)

4 marks

Explain why mutation must be introduced when parent routes have become nearly identical:
Given two parents after multiple generations of order crossover:
$P1: [B, A, G, C, J, D, H, E, F, I]$
$P2: [I, A, G, C, J, D, H, E, F, B]$
1) Recombination stagnation: Both parents share the identical central sub-path $[A, G, C, J, D, H, E, F]$ , differing only in the placement of end cities $B$ and $I$ . Standard crossover operators (OX, CX, PMX) will simply reproduce either P1 or P2, halting evolutionary exploration entirely.
2) Escape from local optima: The population is approaching premature convergence around this specific route structure; without mutation, the algorithm cannot determine whether this tour represents a global optimum or a suboptimal local minimum.
3) Injecting novel diversity: A mutation operator (such as swapping two non-endpoint cities or inverting an intermediate sub-sequence) introduces new topological connections, allowing the search to break out of stagnation without discarding the entire accumulated population.

Mentor tip

Note that nearly identical parents reproduce identical offspring through crossover alone, making mutation essential to break genetic stagnation and escape local minima.

Question 3

6 marks

Comparative evaluation of roulette wheel selection versus tournament selection

Modelling and simulation

6 marks

Evaluate roulette wheel selection against tournament selection for solving the travelling salesman problem:
1) Mechanism of roulette wheel selection: Each route occupies a circular sector proportional to its calculated fitness. A random value selects an individual, giving higher-fitness routes a greater probability of reproducing while maintaining a non-zero probability for less-fit routes to support exploration.
2) Mechanism of tournament selection: A small subset of $k$ individuals is chosen at random from the population, and the single individual with the highest fitness in that sample wins the tournament and enters the mating pool. The process is repeated until the pool is filled.
3) Computational efficiency and scalability: Roulette wheel selection requires calculating the fitness of every individual in the population and performing cumulative sum searches, which becomes computationally expensive for large populations. Tournament selection only evaluates fitness within small subsets ( $k ≪ N$ ), requires no sorting, and parallelizes efficiently across multi-core processors.
4) Selection pressure and convergence control: In roulette wheel selection, if a super-fit individual emerges early, it can monopolize selection and trigger premature convergence; conversely, if fitness values are uniformly high, selection probabilities become nearly equal. In tournament selection, adjusting tournament size $k$ provides direct control over selection pressure: small $k$ preserves diversity, while larger $k$ increases elitism.
5) Direct comparative judgment: Tournament selection generally outperforms roulette wheel selection on large-scale travelling salesman problems because it eliminates costly global population sorting, avoids scaling distortion, and scales seamlessly across parallel computational hardware.

P_{i} = \frac{f _{i}}{\sum _{j = 1}^{N} f _{j}} (Roulette Wheel), Pool = ar g x \in S_{k} max f (x) (Tournament)

Mentor tip

Evaluate both methods across selection mechanics, computational overhead, vulnerability to fitness scaling issues, and parallel scaling capabilities.

Question 4

12 marks

Role of convergence and the exploration-exploitation balance in genetic route optimization

Modelling and simulation

12 marks

Discuss the role of convergence in genetic algorithms and how the balance between exploration and exploitation determines optimization success in route planning:
Concept and dynamics of convergence:
- Definition of convergence: Convergence represents the stage in a genetic algorithm where the population reaches high genetic homogeneity, with the fitness score stabilizing and individual chromosomes becoming virtually identical. Evolution effectively halts because crossover between identical parents generates no new permutations.
- Premature convergence risk: If selection pressure is excessively aggressive or the population lacks diversity, convergence occurs on a suboptimal local minimum early in the search, leaving the true global optimal route undiscovered.
The exploration versus exploitation trade-off:
- Defining exploration: Exploration involves sampling distant, previously unvisited regions of the search space, discovering novel combinations of cities to avoid local traps. In genetic algorithms, exploration is driven primarily by random mutation and exploratory crossover operators.
- Defining exploitation: Exploitation focuses the search within the neighborhood of high-performing solutions already discovered, refining existing successful sub-tours into an optimal configuration. Exploitation is driven by fitness-proportionate selection (favoring high-fitness parents) and elitism.
- Balancing the trade-off: An effective genetic algorithm begins with high exploration (wide search across the problem space) and progressively shifts toward high exploitation (intensively refining the best discovered prospective routes as generations advance).
Fine-tuning convergence via simulated annealing and novelty search:
- Simulated annealing integration: Simulated annealing mimics thermodynamic cooling by maintaining a temperature parameter $T$ . In early generations (high temperature), the algorithm permits inferior neighboring routes with relatively high probability, promoting broad global exploration; as the temperature cools over time, the probability of tolerating worse routes approaches zero, transitioning smoothly to pure local exploitation.
- Novelty search alternative: Novelty search actively rewards behavioral difference (unusual routes) rather than pure distance fitness, preventing premature convergence by driving the population away from crowded local optima.
Role and selection of stopping criteria:
- Halting before stagnation: Because running until complete mathematical convergence can take excessive time, practical implementations use terminating conditions such as fixed generational budgets, computational runtime timeouts, or stagnation criteria (halting after 50 generations without fitness improvement).
Balanced synthesis and conclusion:
Successful route optimization requires managing convergence rather than avoiding it entirely. By initializing a diverse population, starting with high mutation and probabilistic tolerateance (simulated annealing) to drive early exploration, and systematically reducing perturbation rates to favor exploitation as generations progress, the genetic algorithm achieves reliable convergence on a high-quality, near-optimal route within practical computational limits.

P (tolerate worse) = e^{- \frac{Δ E}{T}}

Mentor tip

Thoroughly define convergence and premature convergence, contrast exploration (mutation/crossover) with exploitation (selection/elitism), explain how simulated annealing modulates this balance over time, and conclude on stopping conditions.

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 simulation26 marks · 87%
Q1, Q2, Q3, Q4
System fundamentals4 marks · 13%
Q2

Mentor insights

Traps to watch for

01
Assuming hill climbing always finds the optimal tour · Q1
Hill climbing permits only immediate improvements and gets stuck at the first local minimum it encounters, with no mechanism to escape.
02
Ignoring qualitative race factors in algorithmic route optimization · Q2
A genetic algorithm minimizes numerical distance, but cycling race organization requires managing road safety, spectator access, and civic disruption that distance tables omit.
03
Viewing convergence as an error rather than the intended endpoint · Q4
Convergence is the natural goal where the algorithm settles on an optimal solution; the failure mode is premature convergence on a poor local minimum.

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 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 November 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

Combinatorial optimization principles and local optimum traps in hill climbing

Modelling and simulation

(a)

2 marks

Outline why combinatorial optimization is applied to the travelling salesman problem:
The travelling salesman problem requires discovering the shortest or near-optimal closed tour from a finite, discrete set of permutations of cities.
Because total possible tour permutations grow factorially according to $\frac{( n - 1 )!}{2}$ , exhaustive brute-force search becomes computationally intractable, requiring combinatorial optimization techniques to prune the vast search space and reach feasible solutions quickly.

Permutations = \frac{( n - 1 )!}{2}

Mentor tip

State that combinatorial optimization finds near-optimal tours across discrete permutation sets where exhaustive factorial searches are intractable.

(b)

2 marks

Outline one significant drawback of using simple hill climbing for route optimization:
Susceptibility to local optima: Standard hill climbing only inspects immediate neighboring routes and halts whenever all adjacent single-swap modifications yield inferior tour distances.
Because the algorithm lacks stochastic mechanisms to tolerate temporarily worse solutions or leap across fitness barriers, it becomes permanently trapped on suboptimal local peaks rather than reaching the global optimum.

Mentor tip

Explain that hill climbing halts at the first local optimum because it only tests adjacent neighbors and cannot tolerate worse moves to escape.

Question 2

8 marks

Algorithmic versus manual cycling route design and role of mutation in similar parent tours

System fundamentals
Modelling and simulation

(a)

4 marks

Compare and contrast utilizing a genetic algorithm versus human race organizers for planning a 20-city annual cycling race route:
1) Optimization objective and speed: A genetic algorithm processes millions of distance combinations rapidly and objectively to minimize mathematical route length. Human organizers require days or weeks to draft routes manually and are prone to calculation errors.
2) Qualitative and holistic constraints: Human organizers incorporate real-world safety considerations, road surface quality, elevation gradients, scenic tourist landmarks, spectator viewing accessibility, and municipal traffic disruption. A basic genetic algorithm only optimizes the numerical distance matrix, ignoring qualitative infrastructure factors unless complex penalty functions are programmed.
3) Fairness and neutrality: Algorithmic planning eliminates human bias or favoritism toward specific competitors or teams, whereas human organizers might unconsciously design stages that favor local sprinters or climbers.
4) Social and community disruption: Organizers consult with local city councils and emergency services regarding road closures and local holidays. An unconstrained genetic algorithm might generate impractical routes that isolate hospitals or sever major transport arteries.

Mentor tip

Contrast computational speed and objective distance minimization against vital qualitative factors such as rider safety, road conditions, spectator engagement, and civic logistics.

(b)

4 marks

Explain why mutation must be introduced when parent routes have become nearly identical:
Given two parents after multiple generations of order crossover:
$P1: [B, A, G, C, J, D, H, E, F, I]$
$P2: [I, A, G, C, J, D, H, E, F, B]$
1) Recombination stagnation: Both parents share the identical central sub-path $[A, G, C, J, D, H, E, F]$ , differing only in the placement of end cities $B$ and $I$ . Standard crossover operators (OX, CX, PMX) will simply reproduce either P1 or P2, halting evolutionary exploration entirely.
2) Escape from local optima: The population is approaching premature convergence around this specific route structure; without mutation, the algorithm cannot determine whether this tour represents a global optimum or a suboptimal local minimum.
3) Injecting novel diversity: A mutation operator (such as swapping two non-endpoint cities or inverting an intermediate sub-sequence) introduces new topological connections, allowing the search to break out of stagnation without discarding the entire accumulated population.

Mentor tip

Note that nearly identical parents reproduce identical offspring through crossover alone, making mutation essential to break genetic stagnation and escape local minima.

Question 3

6 marks

Comparative evaluation of roulette wheel selection versus tournament selection

Modelling and simulation

6 marks

Evaluate roulette wheel selection against tournament selection for solving the travelling salesman problem:
1) Mechanism of roulette wheel selection: Each route occupies a circular sector proportional to its calculated fitness. A random value selects an individual, giving higher-fitness routes a greater probability of reproducing while maintaining a non-zero probability for less-fit routes to support exploration.
2) Mechanism of tournament selection: A small subset of $k$ individuals is chosen at random from the population, and the single individual with the highest fitness in that sample wins the tournament and enters the mating pool. The process is repeated until the pool is filled.
3) Computational efficiency and scalability: Roulette wheel selection requires calculating the fitness of every individual in the population and performing cumulative sum searches, which becomes computationally expensive for large populations. Tournament selection only evaluates fitness within small subsets ( $k ≪ N$ ), requires no sorting, and parallelizes efficiently across multi-core processors.
4) Selection pressure and convergence control: In roulette wheel selection, if a super-fit individual emerges early, it can monopolize selection and trigger premature convergence; conversely, if fitness values are uniformly high, selection probabilities become nearly equal. In tournament selection, adjusting tournament size $k$ provides direct control over selection pressure: small $k$ preserves diversity, while larger $k$ increases elitism.
5) Direct comparative judgment: Tournament selection generally outperforms roulette wheel selection on large-scale travelling salesman problems because it eliminates costly global population sorting, avoids scaling distortion, and scales seamlessly across parallel computational hardware.

P_{i} = \frac{f _{i}}{\sum _{j = 1}^{N} f _{j}} (Roulette Wheel), Pool = ar g x \in S_{k} max f (x) (Tournament)

Mentor tip

Evaluate both methods across selection mechanics, computational overhead, vulnerability to fitness scaling issues, and parallel scaling capabilities.

Question 4

12 marks

Role of convergence and the exploration-exploitation balance in genetic route optimization

Modelling and simulation

12 marks

Discuss the role of convergence in genetic algorithms and how the balance between exploration and exploitation determines optimization success in route planning:
Concept and dynamics of convergence:
- Definition of convergence: Convergence represents the stage in a genetic algorithm where the population reaches high genetic homogeneity, with the fitness score stabilizing and individual chromosomes becoming virtually identical. Evolution effectively halts because crossover between identical parents generates no new permutations.
- Premature convergence risk: If selection pressure is excessively aggressive or the population lacks diversity, convergence occurs on a suboptimal local minimum early in the search, leaving the true global optimal route undiscovered.
The exploration versus exploitation trade-off:
- Defining exploration: Exploration involves sampling distant, previously unvisited regions of the search space, discovering novel combinations of cities to avoid local traps. In genetic algorithms, exploration is driven primarily by random mutation and exploratory crossover operators.
- Defining exploitation: Exploitation focuses the search within the neighborhood of high-performing solutions already discovered, refining existing successful sub-tours into an optimal configuration. Exploitation is driven by fitness-proportionate selection (favoring high-fitness parents) and elitism.
- Balancing the trade-off: An effective genetic algorithm begins with high exploration (wide search across the problem space) and progressively shifts toward high exploitation (intensively refining the best discovered prospective routes as generations advance).
Fine-tuning convergence via simulated annealing and novelty search:
- Simulated annealing integration: Simulated annealing mimics thermodynamic cooling by maintaining a temperature parameter $T$ . In early generations (high temperature), the algorithm permits inferior neighboring routes with relatively high probability, promoting broad global exploration; as the temperature cools over time, the probability of tolerating worse routes approaches zero, transitioning smoothly to pure local exploitation.
- Novelty search alternative: Novelty search actively rewards behavioral difference (unusual routes) rather than pure distance fitness, preventing premature convergence by driving the population away from crowded local optima.
Role and selection of stopping criteria:
- Halting before stagnation: Because running until complete mathematical convergence can take excessive time, practical implementations use terminating conditions such as fixed generational budgets, computational runtime timeouts, or stagnation criteria (halting after 50 generations without fitness improvement).
Balanced synthesis and conclusion:
Successful route optimization requires managing convergence rather than avoiding it entirely. By initializing a diverse population, starting with high mutation and probabilistic tolerateance (simulated annealing) to drive early exploration, and systematically reducing perturbation rates to favor exploitation as generations progress, the genetic algorithm achieves reliable convergence on a high-quality, near-optimal route within practical computational limits.

P (tolerate worse) = e^{- \frac{Δ E}{T}}

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 simulation26 marks · 87%
Q1, Q2, Q3, Q4
System fundamentals4 marks · 13%
Q2

Mentor insights

Traps to watch for

01
Assuming hill climbing always finds the optimal tour · Q1
Hill climbing permits only immediate improvements and gets stuck at the first local minimum it encounters, with no mechanism to escape.
02
Ignoring qualitative race factors in algorithmic route optimization · Q2
A genetic algorithm minimizes numerical distance, but cycling race organization requires managing road safety, spectator access, and civic disruption that distance tables omit.
03
Viewing convergence as an error rather than the intended endpoint · Q4
Convergence is the natural goal where the algorithm settles on an optimal solution; the failure mode is premature convergence on a poor local minimum.

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