Revision Library

revisionlibrary.co.uk

A-Level · Paper 2: Algorithms and Programming

A2.1 Elements of Computational Thinking

OCR H446 · Calculators not allowed · about 150 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

Nia Okafor is part of a small software team designing a new online catalogue and booking system for Bramwell Public Library. Members will be able to search the catalogue, reserve books that are currently out on loan, and receive a notification when a reserved book becomes available.

(a)Define what is meant by abstraction as a computational thinking technique.(2)

(b)Define what is meant by decomposition as a computational thinking technique.(2)

(c)Using decomposition, identify three separate sub-problems that Nia's team would need to solve in order to build the library system described above. For one of your three sub-problems, state one piece of detail that could be abstracted away (ignored) at this early design stage.(4)

(Total for Question 1 is 8 marks)

Devon is a software engineer working on an air quality sensor for Marlow Council. Each reading is stored as an 8-bit binary value. To save storage space, repeated identical readings are compressed by recording a value once together with a count of how many times it repeats, an application of pattern recognition in computational thinking.

(a)Convert the denary value 173 to an 8-bit binary number. Show your working.(2)

(b)Convert your answer to part (a) into hexadecimal.(2)

(c)State the name of the pattern recognition technique described above, in which a repeated value is stored once together with a count of how many times it occurs, and state one benefit of using it.(2)

(d)A second sensor reading is recorded as FE in hexadecimal. State this value in binary and in denary.(2)

(Total for Question 2 is 8 marks)

Callum is writing the control program for a vending machine. The machine should display a prompt unless a coin has been inserted AND the selection button has been pressed. His first version of the condition, using two Boolean variables hasCoin and buttonPressed, is:

IF NOT (hasCoin AND buttonPressed) THEN
  OUTPUT "Please insert a coin and press the button"
ENDIF

(a)Complete a truth table for the expression NOT (hasCoin AND buttonPressed) for all four combinations of hasCoin and buttonPressed.(3)

(b)Show that NOT (hasCoin AND buttonPressed) is logically equivalent to (NOT hasCoin) OR (NOT buttonPressed).(3)

(c)Rewrite the IF statement above so that it uses the simplified logical expression from part (b) instead, using OCR Exam Reference Language.(3)

(Total for Question 3 is 9 marks)

Mr Whitfield stores the exam scores for five students in an array called scores, with indices 0 to 4. The initial contents are scores = [67, 45, 89, 23, 71]. He sorts them using the following algorithm:

FOR i <- 0 TO 3
  FOR j <- 0 TO 3 - i
    IF scores[j] > scores[j + 1] THEN
      temp <- scores[j]
      scores[j] <- scores[j + 1]
      scores[j + 1] <- temp
    ENDIF
  NEXT j
NEXT i

(a)Complete a trace table showing the contents of the array scores after each comparison (each value of j) during the first pass of the outer loop, i.e. when i = 0.(4)

(b)State how many comparisons of the IF condition take place during this first pass (i = 0), for this 5 item list.(2)

(c)State an expression, in terms of n, for the total number of comparisons of the IF condition made in the worst case when sorting a list of n items using this algorithm.(2)

(d)The inner loop bound (3 - i) means that, as i increases, fewer comparisons are made in each successive pass. Explain why this is a valid optimisation of the algorithm.(2)

(Total for Question 4 is 10 marks)

Elodie is optimising a program that calculates Fibonacci numbers, where Fibonacci(0) = 0, Fibonacci(1) = 1, and Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) for n ≥ 2. She notices that a simple recursive version recalculates the same values many times over, so she decides to store (cache) results as they are calculated for reuse later, an example of the 'thinking ahead' computational thinking technique.

(a)Define what is meant by memoisation, and state which computational thinking technique it is an example of.(2)

(b)The bottom-up algorithm below calculates Fibonacci(n) by filling an array called cache:

FUNCTION Fibonacci(n)
  DECLARE cache : ARRAY[0:n] OF INTEGER
  cache[0] <- 0
  cache[1] <- 1
  FOR i <- 2 TO n
    cache[i] <- cache[i - 1] + cache[i - 2]
  NEXT i
  RETURN cache[n]
ENDFUNCTION

Complete a trace table showing the value stored in cache[i] for each value of i from 2 to 6, when Fibonacci(6) is called.(3)

(c)Rewrite Fibonacci as a recursive function, in OCR Exam Reference Language, that uses memoisation to avoid recomputing values. You should use a global array called cache, with every element initially set to -1 to show that no value has yet been calculated.(5)

(d)State one other situation in computing, other than calculating Fibonacci numbers, where caching improves performance, and explain why it helps.(2)

(Total for Question 5 is 12 marks)

Zainab is programming a robot to escape a small square maze on a 5 by 5 grid. Columns are numbered x = 0 to 4 (left to right) and rows are numbered y = 0 to 4 (top to bottom). The robot starts at S (0,0) and must reach the exit E (4,4). The function below searches for a path using backtracking, trying directions in the fixed order right, down, left, up:

FUNCTION FindPath(x, y)
  IF grid[x][y] = "E" THEN
    RETURN TRUE
  ENDIF
  IF NOT ValidMove(x, y) THEN
    RETURN FALSE
  ENDIF
  MarkVisited(x, y)
  IF FindPath(x + 1, y) THEN
    RETURN TRUE
  ENDIF
  IF FindPath(x, y + 1) THEN
    RETURN TRUE
  ENDIF
  IF FindPath(x - 1, y) THEN
    RETURN TRUE
  ENDIF
  IF FindPath(x, y - 1) THEN
    RETURN TRUE
  ENDIF
  RETURN FALSE
ENDFUNCTION

ValidMove(x, y) returns TRUE only if (x, y) is inside the grid, is not a wall, and has not already been visited during this search.

(a)Explain what the final line, RETURN FALSE, allows the algorithm to do, and state which computational thinking technique this line is an example of.(2)

(b)Trace the algorithm starting at S(0,0). State the sequence of coordinates visited up to and including the point at which the first backtrack occurs, and state the coordinate to which the algorithm backtracks.(4)

(c)Continuing from the backtrack in part (b), state the full sequence of coordinates that leads the algorithm to the exit E, following the same priority order (right, down, left, up) at each step.(4)

(Total for Question 6 is 10 marks)

Priya drives a delivery van and must visit customers at four locations, A, B, C and D, before returning to the depot P. The table below shows the distance, in km, between each pair of locations:
P-A=4, P-B=9, P-C=7, P-D=6, A-B=5, A-C=8, A-D=3, B-C=2, B-D=10, C-D=6.
Because checking every possible route becomes impractical as the number of locations grows, Priya's route-planning app uses the nearest-neighbour heuristic: starting at the depot, always travel next to the closest location not yet visited.

(a)State why an exact algorithm that checks every possible route becomes impractical as the number of delivery locations increases.(2)

(b)Apply the nearest-neighbour heuristic, starting and ending at the depot P, to find a route visiting A, B, C and D. State the order in which locations are visited and calculate the total distance travelled.(4)

(c)Show that the route P-A-B-C-D-P is shorter than the nearest-neighbour route found in part (b), and explain what this shows about the nearest-neighbour heuristic.(3)

(d)Give one advantage and one disadvantage of using a heuristic approach, such as nearest-neighbour, rather than an exact algorithm for this kind of real-world routing problem.(2)

(Total for Question 7 is 11 marks)

Kestrel Stores is a supermarket chain that analyses transaction data collected through its loyalty card scheme, searching for patterns in what customers buy in order to improve stock control and target promotions.

(a)Define what is meant by data mining.(2)

(b)Big data is often characterised using several 'V' properties. Other than Volume, identify and briefly explain two of these properties, applying each one to Kestrel Stores' transaction data.(4)

(Total for Question 8 is 6 marks)

Kestrel Stores (see the previous question) is considering extending its data mining to build detailed individual customer profiles that could predict sensitive health conditions, such as pregnancy or diabetes, purely from patterns in a customer's purchases, without asking the customer directly. Discuss the ethical issues raised by this proposal, and evaluate whether Kestrel Stores would be justified in using data mining in this way.

(Total for Question 9 is 6 marks)

Kelvin Grove Hospital models patient waiting times at its walk-in triage desk to test how changes might affect the department, without needing to trial them on real patients (performance modelling). One triage nurse (a single server) sees patients strictly in the order they arrive. Five patients arrive at times (in minutes after opening) of 0, 4, 5, 9 and 15, and require treatment (service) times of 6, 3, 5, 4 and 2 minutes respectively. The algorithm below simulates the queue:

arrival[1] <- 0
arrival[2] <- 4
arrival[3] <- 5
arrival[4] <- 9
arrival[5] <- 15
service[1] <- 6
service[2] <- 3
service[3] <- 5
service[4] <- 4
service[5] <- 2
finishPrev <- 0
totalWait <- 0
FOR i <- 1 TO 5
  IF arrival[i] > finishPrev THEN
    start[i] <- arrival[i]
  ELSE
    start[i] <- finishPrev
  ENDIF
  finish[i] <- start[i] + service[i]
  wait[i] <- start[i] - arrival[i]
  finishPrev <- finish[i]
  totalWait <- totalWait + wait[i]
NEXT i

(a)State what is meant by performance modelling as a computational thinking technique, and give one reason it is used instead of trialling changes on the real system.(2)

(b)Complete a trace table showing the values of start[i], finish[i] and wait[i] for i = 1 to 5, and the final value of totalWait, when the algorithm above is executed.(6)

(c)Calculate the mean waiting time per patient across this simulation, giving your answer to 1 decimal place.(3)

(d)Explain why simulating a much larger number of patients would improve the reliability of this performance model's predictions, and suggest one limitation that would remain even with a much larger simulation.(3)

(Total for Question 10 is 14 marks)

A CPU in a laptop used by Kwame's college uses a 4-stage instruction pipeline, Fetch, Decode, Execute and Write-back, to increase throughput by overlapping the execution of successive instructions. Each stage takes exactly one clock cycle, and one clock cycle lasts 2 ns. The processor must execute a program made up of 10 instructions.

(a)State two reasons why pipelining increases the throughput of a processor compared with executing each instruction's stages sequentially, with no overlap between instructions.(2)

(b)Calculate the total time, in ns, to execute all 10 instructions if pipelining is NOT used, i.e. each instruction completes all 4 stages before the next instruction begins.(3)

(c)Calculate the total time, in ns, to execute all 10 instructions using the 4-stage pipeline, assuming no stalls or hazards occur.(3)

(d)Calculate the speed-up factor achieved by using the pipeline for this program, giving your answer correct to 2 decimal places.(2)

(e)State what is meant by a pipeline hazard, and give one example of a situation that could cause the pipeline to stall.(2)

(Total for Question 11 is 12 marks)

Freya analyses monthly visitor numbers for a council website: Jan 1200, Feb 1350, Mar 3100, Apr 1400, May 1450, Jun 1500.

(a)State two reasons why visualising this data (e.g. as a line graph) can make patterns easier to identify than examining the raw numbers alone.(2)

(b)Identify, from the data given, the month that is an outlier compared with the general trend, and suggest a possible real-world cause.(2)

(c)State one type of visualisation, other than a line graph, that would be more appropriate for showing the proportion of the total annual visitors contributed by each month, and justify your choice.(2)

(d)Explain one limitation of relying on visualisation alone, rather than combining it with other computational thinking techniques such as data mining, when analysing very large datasets.(2)

(Total for Question 12 is 8 marks)

Jayden is developing a funds transfer feature for Nexbank's mobile app. Two processes, ProcessA and ProcessB, may run at the same time and both need exclusive access to a shared balanceRecord and a shared transactionLog to complete a transfer:
ProcessA:
LOCK balanceRecord
LOCK transactionLog
// transfer funds
UNLOCK transactionLog
UNLOCK balanceRecord
ProcessB:
LOCK transactionLog
LOCK balanceRecord
// transfer funds
UNLOCK balanceRecord
UNLOCK transactionLog

(a)Define what is meant by 'thinking concurrently' as a computational thinking technique.(2)

(b)Explain, with reference to the pseudocode above, how a deadlock could occur if ProcessA and ProcessB run at the same time.(3)

(c)Suggest a change to the order of the LOCK statements in ProcessB that would prevent this deadlock, and explain why your change works.(3)

(d)State one difference between a deadlock and a race condition.(2)

(Total for Question 13 is 10 marks)

TransitLink is a logistics company whose route-planning software must decide the delivery order for up to 200 stops per van each day. Discuss how a combination of computational thinking techniques, decomposition, abstraction, heuristics and performance modelling, could be applied by TransitLink's developers to produce a workable, efficient solution, and evaluate the trade-offs involved in using approximate (heuristic) methods rather than exact algorithms for a problem of this scale.

(Total for Question 14 is 9 marks)

Mark scheme · A2.1 Elements of Computational Thinking

Question 1

(a) B1 identifies that abstraction involves removing or hiding unnecessary detail from a problem (oe)
(a) B1 identifies that only the detail essential to solving the problem in hand is retained/kept (oe)
(a) Answer: Abstraction is the process of removing unnecessary detail from a problem so that only the information essential to solving it is retained.
(b) B1 identifies that decomposition involves breaking a large/complex problem down (oe)
(b) B1 identifies that it is broken into smaller sub-problems that are easier to solve/manage individually (oe)
(b) Answer: Decomposition is the process of breaking a large, complex problem down into a number of smaller sub-problems, each of which is easier to solve or manage on its own.
(c) B1 valid sub-problem 1, e.g. searching the catalogue for a book by title/author/ISBN
(c) B1 valid sub-problem 2, e.g. placing/managing a reservation on a book that is on loan
(c) B1 valid sub-problem 3, e.g. detecting a reserved book's return and notifying the member
(c) B1 valid abstracted detail linked to one stated sub-problem, e.g. the exact method of sending the notification (email/SMS/app) can be ignored at this stage, as only the requirement to notify the member matters (oe, ft)
(c) Answer: e.g. (1) catalogue search, (2) reservation handling, (3) notification on return; abstracted detail: how the notification is delivered (email/SMS/app) can be ignored at this stage.

Question 2

(a) M1 correct method, e.g. splitting 173 into place values 128+32+8+4+1 (oe)
(a) A1 cao 10101101
(a) Answer: 10101101
(b) M1 splits the byte into two 4-bit nibbles, 1010 and 1101 (oe)
(b) A1 cao AD
(b) Answer: AD
(c) B1 names run-length encoding (RLE)
(c) B1 states a valid benefit, e.g. reduces the amount of storage space/data volume needed (oe)
(c) Answer: Run-length encoding (RLE); it reduces the amount of storage space needed to hold the data.
(d) B1 cao binary 11111110
(d) B1 cao denary 254
(d) Answer: Binary: 11111110, Denary: 254

Question 3

(a) B1 correct hasCoin AND buttonPressed column for all 4 rows (T, F, F, F)
(a) B1 correct NOT(...) column for all 4 rows (F, T, T, T)
(a) B1 all four rows fully correct and consistently laid out
(a) Answer: hasCoin=T,buttonPressed=T: AND=T, NOT=F | T,F: AND=F, NOT=T | F,T: AND=F, NOT=T | F,F: AND=F, NOT=T
(b) M1 states De Morgan's law: NOT (P AND Q) = (NOT P) OR (NOT Q)
(b) M1 correctly substitutes P = hasCoin and Q = buttonPressed
(b) A1 cso - concludes the two expressions are equivalent, consistent with the truth table in part (a)
(b) Answer: NOT (hasCoin AND buttonPressed) = (NOT hasCoin) OR (NOT buttonPressed), by De Morgan's law.
(c) M1 any correct logic: replaces the condition with (NOT hasCoin) OR (NOT buttonPressed)
(c) M1 correct placement of NOT before each variable
(c) A1 structure of IF...THEN...ENDIF and the OUTPUT statement preserved unchanged

IF (NOT hasCoin) OR (NOT buttonPressed) THEN
  OUTPUT "Please insert a coin and press the button"
ENDIF

Question 4

(a) B1 j=0: correctly swaps to give [45, 67, 89, 23, 71]
(a) B1 j=1: no swap, array unchanged [45, 67, 89, 23, 71]
(a) B1 j=2: correctly swaps to give [45, 67, 23, 89, 71]
(a) B1 j=3: correctly swaps to give [45, 67, 23, 71, 89]
(a) Answer: After i=0: [45, 67, 23, 71, 89]
(b) B1 cao 4
(b) B1 correct reason, e.g. j takes the 4 values 0, 1, 2 and 3 so the IF condition is tested 4 times (oe, ft)
(b) Answer: 4 comparisons
(c) M1 recognises the pattern that pass i makes (n-1-i) comparisons, summed over i=0 to n-2 (oe)
(c) A1 cao n(n-1)/2 (oe equivalent forms accepted)
(c) Answer: n(n-1)/2
(d) B1 recognises that after each pass, the largest remaining unsorted value has been moved into its correct position at the end of the unsorted section (oe)
(d) B1 recognises that this position never needs to be compared again, so reducing the range of j reduces the total number of comparisons/improves efficiency without affecting correctness (oe)
(d) Answer: Each pass guarantees the largest unsorted value bubbles into its correct final position, so that position can be excluded from all later passes, reducing the total comparisons made without changing the result.

Question 5

(a) B1 defines memoisation as storing/caching the results of expensive or repeated calculations so they can be reused instead of recalculated (oe)
(a) B1 identifies 'thinking ahead' as the computational thinking technique
(a) Answer: Memoisation is the storing of the results of calculations so that, if the same calculation is needed again, the stored result can be reused instead of being recalculated. It is an example of thinking ahead.
(b) B1 cache[2]=1 and cache[3]=2 both correct
(b) B1 cache[4]=3 and cache[5]=5 both correct
(b) B1 cao cache[6]=8
(b) Answer: cache[2]=1, cache[3]=2, cache[4]=3, cache[5]=5, cache[6]=8
(c) M1 any correct logic: cache array declared/initialised so that every element holds -1 before the function is first called
(c) M1 correct base case: IF n ≤ 1 THEN RETURN n (oe)
(c) M1 correct check: IF cache[n] <> -1 THEN RETURN cache[n] (or equivalent test that a value has already been stored)
(c) M1 correct recursive calculation cache[n] <- Fibonacci(n - 1) + Fibonacci(n - 2) when no cached value exists
(c) M1 correct RETURN cache[n] after the value has been stored; ignore minor syntax errors throughout

FOR i <- 0 TO n
  cache[i] <- -1
NEXT i

FUNCTION Fibonacci(n)
  IF n <= 1 THEN
    RETURN n
  ENDIF
  IF cache[n] <> -1 THEN
    RETURN cache[n]
  ENDIF
  cache[n] <- Fibonacci(n - 1) + Fibonacci(n - 2)
  RETURN cache[n]
ENDFUNCTION

(d) B1 valid example, e.g. a web browser caching images/pages, or a CPU cache storing recently used memory values (oe)
(d) B1 valid reason linked to the example, e.g. avoids the slower process of re-downloading/re-fetching the data from its original, slower source, reducing loading time/improving performance (oe, ft)
(d) Answer: e.g. a web browser caches images so that revisiting a page does not require re-downloading them, reducing loading time, because reading from the local cache is much faster than re-fetching data across a network.

Question 6

(a) B1 explains that it allows the algorithm to undo the last move and return control to the previous call so a different direction can be tried (oe)
(a) B1 identifies backtracking as the computational thinking technique
(a) Answer: It allows the search to backtrack: control returns to the previous call of FindPath so that a different, untried direction can be attempted. This is an example of backtracking.
(b) B1 correctly identifies (1,0) as the first cell visited after S (moving right)
(b) B1 correctly identifies that from (1,0), right and down are both blocked by walls
(b) B1 correctly identifies that left is already visited and up is out of the grid, so (1,0) is a dead end
(b) B1 correctly states that the algorithm backtracks to (0,0) to try the next direction (down)
(b) Answer: Visited: (0,0), (1,0). (1,0) is a dead end (right and down are walls, left is visited, up is out of the grid), so the algorithm backtracks to (0,0).
(c) B1 correctly continues (0,0) - (0,1) - (0,2) - (0,3) after the backtrack (down is tried first each time, as other options are blocked)
(c) B1 correctly continues (1,3) - (2,3), moving right along row y=3
(c) B1 correctly identifies that right from (2,3) is blocked, so the path continues down to (2,4)
(c) B1 cao completes the path (3,4) - (4,4), reaching E
(c) Answer: (0,0) - (0,1) - (0,2) - (0,3) - (1,3) - (2,3) - (2,4) - (3,4) - (4,4) = E

Question 7

(a) B1 identifies that the number of possible routes grows factorially as locations are added (oe)
(a) B1 identifies that this makes checking every route computationally infeasible/take too long for even a moderate number of locations (oe)
(a) Answer: The number of possible routes grows factorially as more locations are added, so checking every route becomes computationally infeasible (takes too long) even for a moderate number of locations.
(b) M1 correct method: at each step, selects the nearest unvisited location from the current location
(b) A1 correct order of visits P-A-D-C-B-P
(b) A1 correct individual distances used (4, 3, 6, 2, 9)
(b) A1 cao total = 24 km
(b) Answer: P - A - D - C - B - P, total distance = 24 km
(c) M1 correctly sums the distances for P-A-B-C-D-P: 4+5+2+6+6
(c) A1 cso 23 km, correctly identified as less than the 24 km found in part (b)
(c) B1 explains that this shows the nearest-neighbour heuristic does not guarantee finding the optimal (shortest) route, only a reasonable one found quickly (oe)
(c) Answer: P-A-B-C-D-P = 4+5+2+6+6 = 23 km, which is less than the 24 km nearest-neighbour route. This shows that the nearest-neighbour heuristic does not always find the optimal route.
(d) B1 valid advantage, e.g. produces a usable route very quickly, even for large numbers of locations, unlike an exact algorithm (oe)
(d) B1 valid disadvantage, e.g. does not guarantee the optimal (shortest) route will be found, as shown in part (c) (oe)
(d) Answer: Advantage: it finds a workable route very quickly, even as the number of delivery locations grows. Disadvantage: it does not guarantee the shortest possible route will be found.

Question 8

(a) B1 identifies that data mining involves analysing/searching through large volumes of data (oe)
(a) B1 identifies that its purpose is to discover previously unknown patterns, trends or relationships within the data (oe)
(a) Answer: Data mining is the process of analysing large volumes of data using computational techniques in order to discover previously unknown patterns, trends or relationships.
(b) B1 names a valid V, e.g. Velocity
(b) B1 applies it to the scenario, e.g. transaction data is generated continuously and rapidly at checkouts across many stores and must be processed at speed (oe)
(b) B1 names a second valid V, e.g. Variety
(b) B1 applies it to the scenario, e.g. the data includes different formats/types, such as structured till receipts alongside unstructured customer feedback (oe)
(b) Answer: Velocity: transaction data is generated continuously and at high speed across all stores, and must be processed quickly. Variety: the data comes in different formats, e.g. structured purchase records alongside unstructured customer service notes.

Question 9

Level 1 (1-2): Identifies a generic or one-sided ethical issue (e.g. privacy) with little or no reference to the Kestrel Stores scenario, and minimal evaluation.
Level 2 (3-4): Identifies more than one relevant ethical issue (e.g. consent, sensitive data, transparency) with some application to the scenario, and attempts an evaluation, though it may be unbalanced or reach no clear conclusion.
Level 3 (5-6): Sustained, balanced discussion of ethical issues (e.g. informed consent, sensitive/health data, transparency, potential for harm) clearly applied to the Kestrel Stores scenario, weighing benefits against risks and reaching a justified evaluative conclusion.
Indicative content:
- Inferring sensitive health information (e.g. pregnancy, diabetes) from purchasing patterns without asking the customer directly raises a privacy/consent issue, since customers are unlikely to expect this level of profiling from a loyalty card.
- Customers may not understand, or have agreed to, this specific use of their data (lack of transparency/informed consent), even if it is technically permitted under the loyalty scheme's terms and conditions.
- Health-related information is a special category of sensitive data; using it to target individuals could cause distress or harm if profiling is inaccurate, or if it reveals a condition to others (e.g. via a mailed offer).
- Counter-argument: used responsibly, in aggregate/anonymised form, such analysis can improve stock control and offer genuinely useful, relevant promotions to customers, and is common commercial practice.
- A justified evaluation should weigh the business/customer benefits against the risk of covert profiling of sensitive characteristics without explicit consent, and may conclude that safeguards such as anonymisation, clear opt-in consent, and transparency would be needed for this to be justified.

Question 10

(a) B1 identifies that performance modelling uses a simplified model/simulation to predict how a system will behave (oe)
(a) B1 valid reason, e.g. cheaper/safer/faster than making changes to and testing a real system, or avoids risk to real patients (oe)
(a) Answer: Performance modelling uses a simplified model or simulation to predict how a system will behave under different conditions. It is used because trialling changes on the real hospital system could be slower, more expensive, or put real patients at risk.
(b) B1 i=1: start=0, finish=6, wait=0
(b) B1 i=2: start=6, finish=9, wait=2
(b) B1 i=3: start=9, finish=14, wait=4
(b) B1 i=4: start=14, finish=18, wait=5
(b) B1 i=5: start=18, finish=20, wait=3
(b) B1 cao totalWait=14
(b) Answer: i=1: start=0,finish=6,wait=0. i=2: start=6,finish=9,wait=2. i=3: start=9,finish=14,wait=4. i=4: start=14,finish=18,wait=5. i=5: start=18,finish=20,wait=3. totalWait=14.
(c) M1 uses totalWait = 14 from part (b)
(c) M1 divides by the number of patients, 5
(c) A1 cao 2.8 minutes
(c) Answer: 2.8 minutes
(d) B1 explains that a larger sample smooths out random variation and is more representative of typical patient arrival/service patterns (oe)
(d) B1 identifies a specific remaining limitation, e.g. the model assumes strict FIFO order and does not account for priority/emergency patients who would be seen out of turn in reality (oe)
(d) B1 further valid development of the limitation or its consequence, e.g. this means the model may still underestimate waiting times for lower priority patients on a busy day (oe, ft)
(d) Answer: A larger simulation averages out random variation in arrival and service times, giving a more reliable, representative prediction. However, it would still assume strict first-come-first-served order and would not model priority/emergency patients being seen out of turn, so it could still underestimate waits for some patients in reality.

Question 11

(a) B1 identifies that while one instruction is at one stage, a different instruction can be at another stage at the same time, so stages are not left idle (oe)
(a) B1 identifies that this increases the number of instructions completed per unit of time / reduces the overall time to complete multiple instructions (oe)
(a) Answer: While one instruction is being decoded, the next instruction can be fetched at the same time (and so on for other stages), so pipeline stages are not left idle; this increases the number of instructions completed per unit time.
(b) M1 correct method: total cycles = number of instructions x number of stages = 10 x 4
(b) A1 correct cycles = 40, multiplied by the clock cycle time of 2 ns
(b) A1 cao 80 ns
(b) Answer: 80 ns
(c) M1 correct method: total cycles = number of stages + (number of instructions - 1) = 4 + 9
(c) A1 correct cycles = 13, multiplied by the clock cycle time of 2 ns
(c) A1 cao 26 ns
(c) Answer: 26 ns
(d) M1 correct method: speed-up = time without pipelining (part b) divided by time with pipelining (part c)
(d) A1 cao awrt 3.08
(d) Answer: 3.08
(e) B1 identifies a pipeline hazard as a situation that prevents the next instruction from executing in its designated clock cycle as planned (oe)
(e) B1 valid example, e.g. a branch instruction whose outcome is not known until the Execute stage, so the processor may have already fetched/decoded the wrong following instructions (control hazard); or an instruction that needs a result from a previous instruction that is not yet available (data hazard)
(e) Answer: A pipeline hazard is a situation that prevents the next instruction executing in its planned clock cycle, e.g. a branch instruction whose outcome is unknown until the Execute stage, meaning instructions fetched after it may have to be discarded and the pipeline stalled.

Question 12

(a) B1 identifies that people can recognise visual patterns/trends more quickly than by reading numeric tables (oe)
(a) B1 identifies that anomalies or outliers stand out immediately in a chart (oe)
(a) Answer: A visual chart lets patterns and trends be spotted at a glance, more quickly than scanning a table of numbers; anomalies or outliers (unusually high or low points) stand out immediately.
(b) B1 identifies March (3100) as the outlier
(b) B1 plausible real-world cause, e.g. a one-off marketing campaign or local news event drove extra visits that month (oe)
(b) Answer: March (3100 visitors) is the outlier; a possible cause is a one-off marketing campaign or news story that temporarily increased visits.
(c) B1 names an appropriate chart, e.g. a pie chart or a stacked bar chart
(c) B1 valid justification, e.g. it clearly shows how each month's share compares to the whole/to the other months (part-to-whole relationship) (oe)
(c) Answer: A pie chart, because it clearly shows how each month's visitor total compares as a proportion of the whole year, rather than showing change over time.
(d) B1 identifies that a chart with a very large number of data points can become cluttered/unreadable, or that the choice of scale can mislead the viewer (oe)
(d) B1 identifies that data mining can uncover subtle patterns/relationships in the data that are not visible to the human eye in a chart (oe)
(d) Answer: With very large datasets, a chart can become too cluttered to read clearly, and misleading scales can distort the apparent pattern. Data mining can uncover subtle patterns or relationships in large datasets that would not be visible simply by looking at a chart.

Question 13

(a) B1 identifies that thinking concurrently involves considering tasks/processes that may run at the same time (oe)
(a) B1 identifies that it involves designing an algorithm/system so that these simultaneous tasks interact correctly, e.g. share resources safely (oe)
(a) Answer: Thinking concurrently means designing an algorithm or system with the understanding that multiple tasks or processes may be running/executing at the same time, and ensuring they interact correctly, for example when sharing resources.
(b) M1 identifies that ProcessA locks balanceRecord while ProcessB locks transactionLog at around the same time
(b) M1 identifies that ProcessA then waits for transactionLog (held by ProcessB), while ProcessB waits for balanceRecord (held by ProcessA)
(b) A1 cao concludes that neither process can proceed, so a deadlock (circular wait) occurs
(b) Answer: ProcessA locks balanceRecord while ProcessB locks transactionLog at almost the same time. ProcessA then waits to lock transactionLog, which ProcessB is holding, while ProcessB waits to lock balanceRecord, which ProcessA is holding. Neither process can proceed, so a deadlock occurs.
(c) B1 correctly suggests reordering ProcessB to LOCK balanceRecord before LOCK transactionLog (i.e. the same order as ProcessA)
(c) B1 explains that both processes now request the shared resources in the same order, so whichever process locks balanceRecord first will be able to acquire transactionLog before the other process can request it (oe)
(c) B1 further valid development, e.g. identifies this as an example of the general deadlock-prevention technique of enforcing a consistent lock ordering/hierarchy (oe)
(c) Answer: Reorder ProcessB to LOCK balanceRecord then LOCK transactionLog, the same order as ProcessA. Because both processes now request the two resources in the same order, one process will always obtain both locks in turn without the other holding one it needs, removing the circular wait. This is a standard deadlock-prevention technique: enforcing a consistent lock ordering.
(d) B1 correctly describes deadlock, e.g. two or more processes are permanently blocked, each waiting for a resource held by another (oe)
(d) B1 correctly describes a race condition, e.g. processes do complete, but the final result depends unpredictably on the timing/order in which they access shared data, and may be incorrect/inconsistent (oe)
(d) Answer: In a deadlock, two or more processes are permanently blocked, each waiting for a resource held by the other, so none can proceed. In a race condition, the processes do complete, but the outcome depends unpredictably on the exact timing/order of access to shared data, which can produce an incorrect or inconsistent result.

Question 14

Level 1 (1-3): Limited or generic discussion, largely descriptive rather than applied to the TransitLink scenario; little or no evaluation of the heuristic versus exact trade-off; technical terminology used inconsistently.
Level 2 (4-6): Reasonable discussion of at least two computational thinking techniques, applied with some success to the scenario; some evaluation of the heuristic versus exact trade-off, though it may be one-sided or underdeveloped; mostly appropriate terminology.
Level 3 (7-9): Detailed, coherent discussion of at least three computational thinking techniques, accurately applied to the TransitLink scenario; balanced evaluation of the trade-offs between heuristic and exact approaches, reaching a justified conclusion; technical terminology used accurately throughout.
Indicative content:
- Decomposition: the overall route-planning problem can be broken down into smaller sub-problems, e.g. first grouping stops by depot/geographic zone, then deciding the delivery order within each zone.
- Abstraction: the algorithm can ignore irrelevant detail (e.g. individual driver preferences, exact parcel contents) while retaining the essential detail needed to plan a route (e.g. delivery time windows, road distances/times between stops).
- Heuristics: an exact algorithm checking every possible order of up to 200 stops is computationally infeasible, since the number of possible routes grows factorially; a heuristic (e.g. nearest-neighbour, or an improvement heuristic such as 2-opt) can produce a good, workable route in a practical amount of time.
- Performance modelling: a simulation of proposed routes (e.g. under varying traffic conditions or van breakdowns) can be used to test how well a route plan is likely to perform in practice before it is used operationally, without the cost/risk of testing on real deliveries.
- Evaluation of trade-off: heuristic methods are fast and scale well to large numbers of stops, but do not guarantee an optimal (shortest/cheapest) route; exact algorithms guarantee optimality but become impractical well before 200 stops are reached, so a combination of techniques (decomposition to reduce problem size, then heuristics within each sub-problem, refined and tested by performance modelling) is an appropriate, justified real-world solution given the operational need for near real-time route generation.

Elements of Computational Thinking - Worksheets, Questions and Revision