A Level Computer Science Paper 2: Algorithms and Programming

Representational abstraction removes detail from a situation until only the information needed to solve the specific problem remains. A map of the Underground is the standard example, discarding real distances, geography and everything above ground while retaining exactly what a passenger needs: the order of stations and where lines interchange. Abstraction by generalisation instead groups different things according to characteristics they share so that a single solution serves all of them. Defining a Shape superclass with an area method, from which Circle, Square and Triangle inherit, is an example: code written to work with Shape then works with every kind of shape, including ones added later, without being rewritten.

def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2) The base case returns n directly when n is 0 or 1, which stops the recursion, and the general case returns the sum of the two preceding terms. An iterative version is strongly preferable for large n for two reasons. First, the naive recursive version recalculates the same subproblems an enormous number of times: computing the tenth term requires computing the eighth twice, the seventh three times and so on, and the total number of calls grows exponentially, so even a modest n such as 40 takes a noticeable time and n of 60 is entirely impractical. Second, every call adds a stack frame holding its parameters and return address, and those frames accumulate until the recursion unwinds, so deep recursion risks exhausting the stack. An iterative version keeps only the two most recent terms in variables and loops forward, which runs in linear time with constant memory and handles large n instantly.

Passing by reference means the subroutine is given the memory address of the caller's data rather than a copy of the data itself, so any modification the subroutine makes is made directly to the original and persists after the subroutine returns. The advantage is efficiency: no copy is created, so passing a large array or object costs the same as passing a single address rather than duplicating potentially megabytes of data, and it also allows the subroutine to return several results by modifying the variables it was given. The disadvantage is that side effects become possible, since a subroutine can alter data the caller did not expect it to touch, and this makes the program considerably harder to reason about and to debug because a variable's value can change without any assignment appearing in the calling code.

Quicksort selects one element of the list as the pivot and then partitions the remaining elements so that all values smaller than the pivot are placed to its left and all larger values to its right, which puts the pivot into its final correct position. The two partitions are then sorted recursively by exactly the same method, and because a single item partition is already sorted, the recursion terminates. On average each partition divides the data roughly in half, giving about log n levels of recursion with n comparisons at each level, so the average time complexity is O(n log n), and in practice quicksort usually outperforms merge sort because its constant factors are smaller and it partitions in place. The worst case is O(n squared) and occurs when the pivot chosen is consistently the smallest or largest remaining element, because each partition then removes only one item rather than halving the data, producing n levels of recursion. The classic way this happens is choosing the first element as the pivot on data that is already sorted or reverse sorted, which is why practical implementations select the pivot at random or as the median of three sampled values.

Dijkstra's algorithm initialises the distance to the source node as zero and to every other node as infinity, with all nodes unvisited. It then repeatedly selects the unvisited node with the smallest recorded distance and treats it as the current node. For each unvisited neighbour of that node it calculates the distance reached by travelling through the current node, which is the current node's distance plus the weight of the connecting edge, and if this is smaller than the neighbour's recorded distance then the record is updated and the current node is stored as that neighbour's predecessor. The current node is then marked as visited, since its distance is now known to be final, and the process repeats until the destination has been visited or no reachable unvisited node remains. The path itself is recovered by following the chain of predecessors backwards from the destination. The principal limitation is that the algorithm cannot handle negative edge weights, because its correctness rests on the assumption that once a node is marked visited no shorter route to it can be found later, and a negative edge encountered subsequently could invalidate exactly that assumption.

A linear search has complexity O(n), so with two million items it would examine on average a million entries per query, and at thousands of queries per second this is entirely impractical however simple it is to implement. Its only advantage is that it requires no ordering and no preparation. A binary search has complexity O(log n), reducing the work to about twenty one comparisons since two to the power twenty one exceeds two million, which is an improvement of roughly five orders of magnitude. Its precondition is that the collection is maintained in sorted order, which means either a one off sort at O(n log n) if the data is static, or an ongoing insertion cost, since inserting into a sorted array requires shifting subsequent elements. A hash table gives average O(1) lookup, because the hash function calculates the storage position directly from the key so no searching occurs at all, and the time taken does not increase with the size of the collection. For pure membership testing at this frequency the hash table is clearly the best choice, provided a good hash function is used and the load factor is kept low enough that collisions remain rare. The one consideration against it is that a hash table imposes no useful ordering, so if the system also needs sorted output or range queries then a balanced binary search tree, giving O(log n) for both lookup and in order traversal, would be the better overall structure.

A heuristic is a rule of thumb that guides a search towards a good solution quickly, without any guarantee that the solution found is the best one available. It is appropriate whenever finding the genuinely optimal answer would require exploring so many possibilities that the computation is infeasible within an acceptable time. Route finding illustrates this well. A satnav could in principle evaluate every possible sequence of roads between two points and select the shortest, but the number of possibilities in a national road network is astronomically large. Instead the A star algorithm uses the straight line distance to the destination as a heuristic to decide which routes look most promising and explores those first, ignoring directions that lead away from the target. A route is produced in a fraction of a second and is optimal or very close to it, and a driver waiting at a junction is far better served by an excellent answer immediately than a perfect one after an hour of computation.

Breadth first search must visit every node at the current depth before moving on to any node at the next depth, which means nodes should be processed in exactly the order in which they were discovered. A queue is first in first out, so the node that has been waiting longest is always the next one taken, and since nodes at the current level are discovered before nodes at the next level, the queue naturally produces level by level exploration. Depth first search must follow one path as far as it goes before backtracking to try an alternative, which means the node most recently discovered should be the next one explored. A stack is last in first out, so pushing each newly discovered node and popping the top gives exactly that behaviour, and when a path reaches a dead end the stack automatically returns to the most recent unexplored branch, which is the backtracking the algorithm requires.

The problem is that the total number of lines does not change while the loop runs, yet the program recalculates it on every single iteration by reopening and completely re-reading the file. If the file contains n lines, the outer loop runs n times and each iteration reads n lines, so the program performs n squared read operations instead of n, turning a linear task into a quadratic one. This is particularly costly because file access involves the operating system and secondary storage and is orders of magnitude slower than operations on data already in memory, so the effect on a large file is severe. The correct restructuring is an application of thinking ahead: any calculation whose result does not change during a loop should be moved out of it. The program should count the lines once before the loop begins, or better still read the file once into a list and take its length, store that value in a variable, and then simply refer to that variable inside the loop. This reduces the program to a single pass over the file.

Time complexity describes how the number of operations an algorithm performs grows as the size of its input increases, while space complexity describes how the amount of memory it requires grows with that input. The two frequently conflict, because many techniques for reducing time work by storing additional information. Sorting provides a clear example. Merge sort has time complexity O(n log n) in every case, which is dramatically better than bubble sort's O(n squared), so on a million items merge sort is faster by a factor of tens of thousands. However, merge sort must create and hold the sub lists produced during the divide and merge phases, giving it space complexity O(n), whereas bubble sort operates entirely within the original array using a single temporary variable and therefore has space complexity O(1). On a general purpose machine sorting a large array the time saving is overwhelmingly worth the memory, but on an embedded device with a few kilobytes of RAM the additional allocation may simply be unavailable, and the slower in place algorithm becomes the only viable option.

The principal benefit of concurrency is that parts of a task which do not depend on one another can execute at the same time rather than sequentially, so the total elapsed time falls and the available processor cores are used fully rather than sitting idle. Work such as rendering the individual frames of an animation, applying a filter to a large set of images or serving independent requests on a web server parallelises almost perfectly, because each unit of work is entirely self contained. A second benefit is responsiveness: running long computation on a separate thread allows a user interface to continue reacting to input rather than freezing, which is often the reason concurrency is introduced even when no speedup is expected. The difficulties are substantial and they are of two kinds. The first kind concerns how much benefit is actually available. Only the portion of the work that can genuinely be divided gains anything, and Amdahl's law states that whatever fraction must remain sequential sets a hard ceiling on the achievable speedup no matter how many processors are added, so a task that is twenty per cent sequential can never be more than five times faster. Data dependencies restrict division further, because any operation requiring the result of a previous one must wait for it, and the coordination overhead of creating threads, distributing work and gathering results grows as more threads are added, eventually outweighing the gain. The second kind of difficulty concerns correctness, and it is the more serious. Where threads share mutable data, race conditions become possible: if two threads read, modify and write the same value without synchronisation, the final result depends on the precise order in which their operations interleave, so the program may produce the right answer in testing and the wrong one occasionally in production, and such faults are extremely difficult to reproduce and diagnose. Preventing this requires locks, which introduce the possibility of deadlock when two threads each hold a resource the other is waiting for, and which reduce the very parallelism they were introduced to protect. Concurrent code is therefore markedly harder to write, test, debug and reason about than sequential code. Concurrency is justified when the work divides into genuinely independent units, when the sequential fraction is small, and when the resulting time saving is large enough to repay the substantial additional complexity. Where those conditions do not hold, and particularly where correctness matters more than speed, a straightforward sequential design is usually the better engineering decision.

A precondition is a statement that must be true at the moment a subroutine is called if that subroutine is to behave correctly. It expresses an assumption the subroutine relies on rather than one it checks, so it places an obligation on the calling code. A binary search, for example, has the precondition that the array passed to it is sorted in ascending order, because it decides which half of the range to discard on precisely that assumption. Documenting preconditions matters because a violated precondition frequently produces no error at all: a binary search on unsorted data runs perfectly happily and simply returns wrong answers, reporting that present items are absent. A fault that announces itself is far cheaper than one that quietly corrupts results, so making the obligation explicit in the documentation lets the caller guarantee it, and it also allows a maintainer to understand why the subroutine is written as it is rather than adding defensive checks that would slow it down unnecessarily.

Polymorphism means that objects of different classes, related through a common superclass or interface, all respond to the same method call, with each class providing its own implementation of that method. Existing code can therefore call the method on a collection of such objects without ever examining what type each one actually is, because the correct implementation is selected at run time by the object itself. The consequence is that adding new functionality requires only that a new class be written which implements the expected interface. A game loop that calls update on every object in a list continues to work correctly when a new kind of enemy is added, because the new class simply provides its own update, and not a single line of the loop needs to change. Without polymorphism the loop would need a conditional branch for every possible type, and adding a new type would mean finding and modifying every such loop throughout the program, which is both laborious and a reliable source of defects when one is missed.