Elements of Computational Thinking

1 Explain the difference between representational abstraction and abstraction by generalisation. 4

One mark for each of the following, to a maximum of 4.

• Representational abstraction removes detail until only what is needed remains
• Gives an example such as a map or a model
• Abstraction by generalisation groups things by shared characteristics
• Gives an example such as a superclass serving several subclasses

Model answer. Representational abstraction is the process of removing detail from a situation until only the information needed to solve the problem remains. A map of the London Underground is the classic example: it discards real distances, geographic direction and everything above ground, keeping only the order of stations and where lines interchange, which is precisely what a passenger needs and nothing more. Abstraction by generalisation instead groups different things together according to characteristics they share, so that one solution can serve all of them. Defining a Vehicle class with attributes and methods common to cars, vans and lorries is an example, since code written to work with Vehicle then works for every kind of vehicle without being rewritten for each.

2 Explain what is meant by a precondition and give an example. 3

One mark for each of the following, to a maximum of 3.

• A condition that must be true before a subroutine is called for it to work correctly
• Gives a valid example such as a sorted array for binary search
• Explains that if it is not met the result is incorrect or the program fails

Model answer. A precondition is a statement that must be true before a subroutine is called if that subroutine is to work correctly. It documents an assumption the subroutine makes rather than checks. For example, a binary search has the precondition that the array passed to it is already sorted in ascending order, because the algorithm decides which half to discard on the assumption that everything to the left of the midpoint is smaller. If that precondition is not met the search will still run and return a result, but the result will simply be wrong, and no error will be raised to indicate that anything went astray, which is why preconditions must be stated explicitly and guaranteed by the calling code.

3 Explain the benefits and difficulties of concurrent processing. 6

One mark for each of the following, to a maximum of 6.

• Independent parts of a task can be executed at the same time
• The total execution time is reduced and processor resources are used more fully
• A system can remain responsive while long work continues in the background
• Only the parallelisable portion benefits, and Amdahl's law limits the gain
• Race conditions can occur where the result depends on the timing of access to shared data
• Deadlock and synchronisation overhead make concurrent code harder to write and debug

Model answer. The benefit of concurrent processing is that parts of a task which do not depend on one another can be executed at the same time rather than one after another, so the total elapsed time falls and the available processing resources are used far more fully. Rendering the separate frames of an animation is a clear case, since each frame can be computed entirely independently. Concurrency also allows a system to stay responsive, running a long calculation on one thread while the user interface continues to react on another. The difficulties are substantial. Only the portion of the work that can genuinely be divided benefits, and Amdahl's law states that whatever fraction must remain sequential sets a hard ceiling on the achievable speedup regardless of how many processors are added. Data dependencies limit division further, since a step requiring the result of an earlier one cannot begin until that step has finished. Where threads share data, race conditions become possible: if two threads read, modify and write the same value without proper synchronisation, the final result depends on the order in which their operations happen to interleave, and the fault may appear only occasionally and only under particular timings, which makes it exceptionally difficult to reproduce and diagnose. Preventing this with locks introduces the risk of deadlock, where two threads each hold a resource the other is waiting for so neither can continue. Finally, the synchronisation itself consumes time, and concurrent code is significantly harder to write, test and reason about than sequential code, so the complexity cost must be genuinely repaid by the time saved.

4 A program processes a large set of images, applying the same filter to each one, and then produces a single report summarising all of them. Explain which parts of this could be executed concurrently and which could not. 4

One mark for each of the following, to a maximum of 4.

• Applying the filter to each image is independent so images can be processed concurrently
• No image's result depends on any other image
• Producing the summary report cannot begin until all images are processed
• The report is a data dependency, forcing that part to be sequential

Model answer. Applying the filter to the images is an ideal candidate for concurrent execution, because each image is processed entirely independently of every other one. Nothing about filtering image five depends on the outcome of filtering image four, so the set can be divided between as many threads or processors as are available, and the total time for that stage falls roughly in proportion to the number of workers used. Producing the summary report is different. It aggregates information drawn from every image, so it cannot begin until every image has been processed, which makes it a data dependency that forces the program back into sequential execution at that point. In practice the report generation itself is also likely to be a single sequential operation, and it is precisely this kind of unavoidable sequential section that Amdahl's law identifies as the limit on the overall speedup achievable.

5 Explain why a computational model of a real world system may produce inaccurate predictions. 3

One mark for each of the following, to a maximum of 3.

• A model is necessarily a simplification of the reality
• Detail judged irrelevant is removed, but it may turn out to matter
• Assumptions made in the model may not hold in reality

Model answer. A computational model is by definition a simplification of the system it represents, since a model containing every detail of reality would be as complex as reality itself and therefore useless. Building it requires choosing which details are relevant and discarding the rest, and the accuracy of the model depends entirely on whether those choices were right. Detail that was judged irrelevant may in fact influence the outcome, and factors omitted altogether cannot be predicted at all. Beyond omission, models rest on assumptions about how the system behaves, and those assumptions may simply not hold: a traffic model assuming every driver chooses the objectively fastest route will underestimate congestion, because real drivers act on habit and incomplete information. The model can therefore be internally correct and still produce predictions that do not match what actually happens.