Note: I've just migrated to a different physical server to run Spivey's Corner,
with a new architecture, a new operating system, a new version of PHP, and an updated version of MediaWiki.
Please let me know if anything needs adjustment! – Mike

AQA 2019 Paper 1

Copyright © 2024 J. M. Spivey
Jump to navigation Jump to search

Queston 1: Bubblesort

The question concerns the following implementation of bubble-sort, expressed in 'pseudo-code'.

PROCEDURE BubbleSort(L)
   N ← LEN(L) – 2
   Count1 ← 0
   WHILE Count1 < LEN(L) – 1
      FOR Count2 ← 0 TO N
         IF L[Count2] > L[Count2 + 1] THEN
            Temp ← L[Count2]
            L[Count2] ← L[Count2 + 1]
            L[Count2 + 1] ← Temp
         ENDIF
      ENDFOR
      Count1 ← Count1 + 1
   ENDWHILE
ENDPROCEDURE

In pseudocode, there's no reason for the tedious sequence of assignments involving Temp; it would be better to write simply

            SWAP L[Count2], L[Count2+1]

Other stylistic points could be made: for example, Count1 and Count2 are poor choices for local variables because the prefix Count contains no useful information, and the two names differ only in the suffix 1 or 2. Variables named I and J would be better all round. Also, there's no reason to introduce the variable N with its curious value LEN(L)-2, except as a stepping stone for what it to come. Likewise, the choice to express one loop and a WHILE and the other as a FOR is explained only as a stepping stone to changing the program later.

There's actually no reason to introduce pseudo-code for a program like this, since the same program could be expressed with little change in an ordinary programming language such as Python. The more pedantic conventions – ENDWHILE, ENDPROCEDURE, for assignments – that are introduced in pseudo-code, the more it becomes just a nuisance.

We are invited (Q1.1) to suggest speeding the program up, first by taking advantage of the fact that the largest remaining element is moved to the end in each pass, so that successive passes can scan shorter and shorter segments of the array. This is achieved by decrementing the variable N after each pass. (This observation makes bubble-sort into a baroque version of selection sort.) Secondly, the whole algorithm can finish early if any pass succeeds in making no changes to the array, and that idea can be implemented by introducing a flag Done, set just before each pass and cleared whenever a swap is made. These changes do indeed improve the running time of the program, by approximately a factor of 2 for the first change, and for the second change by an amount whose expected value is hard to determine. The second change is of little or no help in the common situation of adding some fresh elements to the end of an already sorted array and then sorting them into place, for a weakness of bubble-sort is that it can move any element only one place to the left in each pass.

In (Q1.2) we must quote the conventional definition of 'feasible' as 'achievable in polynomial time' and observe that even a quadratic algorithm establishes that sorting is feasible. A more critical approach would observe that an algorithm with running time \(O(N^{10^10})\) is polynomial alright, but hardly feasible in any practical sense. Even quadratic algorithms are of dubious value when the problem grows very large. (Q1.3) has the one-word answer "heuristics", though it's not clear that candidates are required to be able even to name a heuristic algorithm for any problem.

But these minor points do not uncover the real issue: that there is no reason to teach bubble-sort to beginning programmers. It is slow, even compared with other [math]\displaystyle{ O(N^2) }[/math] sorting algorithms, complicated to implement, and very difficult to analyse in a perspicuous way, either for its correctness or its performance. To see that bubble-sort is correct, we must either deal with the number of inversions in a permutation, observing that each swap reduces the number of inversions by one; or we must make the observation that each pass moves the largest remaining element to the end, making bubble-sort effectively a bad implementation of selection sort. The effect of changes such as those listed above on the running time is hard to quantify. By way of contrast, a simpler algorithm like insertion sort is clearer to implement, easier to explain, maintains a much more simple invariant, and runs much more quickly, especially bearing in mind the memory hierarchy of modern machines. To quote a comment Knuth wrote somewhere, "Don't let me catch you using bubble-sort again!"

Question 2: Turing machines

In this question, we are supposed (Q2.1) to complete the trace of a Turing machine execution, and recognise (Q2.2) that the machine has the effect of duplicating a block of ones into the blank space to its right, before (Q2.3) halting on the zero immediately to the left of its original cell. Then we must (Q2.4) quote the definition of the term 'universal Turing machine' without doing anything with it.

Question papers from other years have had a similarly superficial treatment of Turing machines, requiring us to say for example that the Halting Problem cannot be solved by any Turing machine because it is Unsolvable. To make them a proper part of a computer science curriculum, links need to be made explicit between Turing machines and conventional models of computation. We need to know, for example, that a 'feasible' algorithm on a register machine remains feasible when simulated on a Turing machine (because each primitive operation can be simulated in polynomial time). Or to see that the existence of a universal machine implies that there is a single program whose halting on any input is undecidable. Also, to know about some other unsolvable problems apart from the Halting Problem, or about a range of infeasible (= NP-hard) problems that flow from SAT by a chain of problem reductions. Without such content, we are just learning a few words and gaining a smattering of

Question 3: Sudoku

This question invites us to think about the reduction of Sudoku to graph-coloring. Except that, curiously, graph coloring is never mentioned in the question, and the graph concerned is given to us in the question as an adjacency matrix. We are asked (Q3.1) to finish a nearly-complete Sudoku puzzle, then to recognise that the graph is both (Q3.2) a "representational abstraction" because it removes unnecessary details, and (Q3.3) an "abstraction by generalisation" because all adjacency relationships (Q3.4) are treated on an equal footing, whether they arise from squares in the same row, the same column, or the same block. We must say (Q3.5) that adjacency lists may be preferable to a full adjacency matrix when the graph is sparse, and that (Q3.6) a directed graph would give rise to an adjacency matrix that need not be symmetric.

We are not invited to think about whether graph coloring is a feasible problem (it isn't), whether there are useful heuristics (there are, and they make sense for Sudoku), or to engage with the heart of the problem in any significant way.

Question 4: Regular expressions

We are asked to say (Q4.1) that * stands for repetition and (Q4.2) ? for an optional element in regular expressions – though the ? operator is not part of the usual mathematical definition of a regular expression, but merely a convention (useful enough) adpoted by some computer representations. We must recognise (Q4.3) which of a list of strings are described by the regular expression 1|01+; this part of the question hinges significantly on the knowledge (merely a matter of convention) that the regular expression in question is to be read as 1|(0(1+)) and not as (1|0)(1+), rather than on any deeper properties of regular expressions.

Question 5: Programming task

This question asks us to implement a check that one word can be made with the letters of another. The task is quite straightforward, although one can think of varipus approaches that will have different running times. For example, one could count the number of occurrences of each letter in the first word and in the second, and then verify that the count of each letter was no greater in one word than in the other. The counts could be kept in an array, and for a fixed-size alphabet, the entire program would then run in a time linear in the combined length of the strings. We all know that \(O(26) = O(1)\), don't we? But that's probably overthinking the question, and it might be enough to check, for each character of the first string, that its count in the first string is no greater than its count in the second. This solution will be \(O(N^2)\) where \(N\) bounds the length of the strings, but that's probably good enough.

The key to a clean solution (though not one followed in the model answer) is to introduce appropriate subroutines, certainly separating the solution to the problem from the main program's I/O for testing, but also if necessary using a subroutine for the repeated task of counting occurrences of a character in a string. The model answer doesn't do this, and mashes all the code together into one complex blob, as if the pressure of an exam is just cause for abandoning a systematic approach. Just the opposite!

Here's my solution written in Python, with the caveat that I don't know Python very well.

# count -- count occurrences of character in a string
def count(c, s):
  n = 0
  for i in range(0, len(s)):
    if s[i] == c:
      n += 1
  return n

# canmake -- test whether one string can be made from another
def canmake(w1, w2):
  for i in range(0, len(w1)):
    c = w1[i]
    if count(c, w1) > count(c, w2):
      return False
  return True

# unit -- unit test for canmake
def unit(w1, w2, exp):
  res = canmake(w1, w2)
  success = "Pass" if res == exp else "Fail"
  print(f'canmake({w1}, {w2}) = {res}: {success}')

# Two examples
unit('NINE', 'ELEPHANTINE', True)
unit('NINE', 'ELEPHANT', False)

Some notes:

  1. I've omitted the interaction, "Gimme one string?", "Gimme another string?", and replaced it with a couple of unit tests. (I just can't bring myself to write that stuff).
  2. Nevertheless, the job of computing the result is in a subroutine separate from the main program or the unit test harness. In that subroutine, canmake, I've used the idiom of an early return from a loop to produce the result as soon as it is known. In a tiny subroutine like this, the effect of that idiom is easy to see.
  3. I've added another subroutine count that counts occurrences of a character in a string. If I knew Python better, I would know I could write s.count(c) in place of count(c, s), using a built-in method of strings in Python. But that's not the point, because introducing a well-chosen subroutine encapsulates the complexity of computing the counts for ourselves.
  4. Each subroutine in the program is a handful of lines long, and has a clear purpose expressible in a one-line comment. Such comments can be gathered and used as an index for a larger program.

Question 6: Binary files

We are asked why a computer game might save its session data in a binary file rather than a text file. One answer is that this saves the time and complication of converting the data to and from a textual representation. But the most favoured answer seems to be that it prevents a casual observer from knowing what is saved in the file. Isn't that just promoting security by obscurity? Significant disadvantages of a binary file format would include the difficulty of porting it between platforms or between versions of the program, and the difficulty of detecting when the file has become corrupted, particularly after multiple cycles of loading and saving the game.

Question 7: GetIndexOfItem

We are asked comprehension questions about a subroutine GetIndexOfItem whose source code I do not have. Apparently this subroutine takes both an item id and a name as parameters. It returns (Q7.1) a value of -1 if the item is not found, a clear enough convention. But it appears able to search both by id and by name, using the name (Q7.2) if the id is specified as -1. This seems a dubious design decision to me, making the interface of the subroutine fussy and its implementation slow, when compared to a solution where search by id and search by name were two separate subroutines.

The body of GetIndexOfItem performs a linear search (Q7.3), and that is OK. Either it is written as a single loop, in which case the loop body must repeatedly make a complex test that slows it down; or the body is made of two loops, one searching by id and the other searching by name – in which case it may as well become two separate subroutines for simplicity and clarity. Evidently (Q7.4) searching by name can give ambiguous results if two or more items can have the same name.

We are asked (Q7.5) to consider using a hash table indexed by ID to speed one kind of search, though one hash table could not (Q7.6) speed up search for both attributes.

Some points should be made about the naming of Get-Index-Of-Item. It's generally a bad idea to name a subroutine that returns something with an imperative name, and especially so if the imperative is made by prepending Get to a desciption of the value returned. So let's make it Index-Of-Item. But more than that, the suffix Of-Item isn't very informative, and longer identifiers do not help much unless the length adds useful information. So let's drop it, and agree to have two subroutines named IndexForName and IndexForID.

Question 8: Set algebra

This question seems to introduce naive set theory gratuitously to in a way that does not really illuminate the program. We must explain (Q8.1) that the set \(X\) of items that the player can subject to the command "use" is the intersection of the set \(B\) of items that understand that command with the union of the items in the player's inventory and the items at their current location that have a status of usable. Next (Q8.2), this set \(x\) is a proper subset of both the set \(A\) of all items, and the set \(B\) – though I don't see why all items that understand the "use" command should not be usable if they all happen to be located where the player is. The sense of (Q8.3) completely escapes me, but may be clear from the supplied code. Finally (Q8.4), we are to define the term proper subset, though we have already used it.

Question 9: Program structure

In this comprehension question, we are supposed to notice (Q9.1) that Main calls LoadGame and (Q9.2) PlayGame, and (Q9.3) that the LoadGame and IsNumeric subrotines involve exception handling.

We must distinguish (Q9.4) local and global variables, though without (reading the model answer) making any clear distinction between scope, extent and visibility, and must say (Q9.5) why it is "good practice" to use local variables.

Question 10: PlayGame

Here we must modify the program so that in one circumstance it displays not a single, fixed error message, but one of two error messages chosen at random. The task here is extremely specific, and a well-engineered answer must address the question what other, similar changes can be anticipated. We must ask:

  • Are there other error messages in the program that should be replaced with a random selection?
  • Must it be a choice of two error messages, or will a longer list of random messages sometimes be needed?
  • Will error messages be rare enough that we need not worry too much about the time taken to produce them? For example, if there is a choice of messages, is it acceptable to format them all before choosing one to output?

My Python solution is to introduce a subroutine randmessage that takes a list of messages and prints one of them at random.

import random

# randmessage -- output random error message
def randmessage(msglist):
  i = random.randint(0, len(msglist)-1)
  print(msglist[i])

command = "jostle"
randmessage([f"Sorry, I don't know how to {command}.",
             f"I'm afraid I can't {command}, Dave.",
             f"My doctor has forbidden me to {command}."])

The minor disadvantage of this scheme is that all the format strings in the list will be processed, but only one of them will be selected for output. A great advantage is that a call to randmessage can be easily substituted for a call to print wherever a random message is wanted in the program, without replicating the mechanism for random selection. We could introduce refinements in the subroutine, such as ensuring the same message was never printed twice in a row, without having to change every place where randmessage was called.

Question 11: GetItem

This question asks us to enhance the subroutine GetItem so that an attempt to pick up another item fails if there are already five items in hand. The only complication appears to be that to determine how many items are in hand, we must example all the items in the game and count how many of them have a location field set to the value INVENTORY. This cries out for a subroutine, either ItemsInHand() or ItemsAtLoc(INVENTORY), which will no doubt have applications elsewhere once we become interested in counting items.

Question 12: DropItem

Now we must introduce a command to drop and item at the current location, which entertainingly may break if it is fragile. The model answer reveals that the command interpreter is structured with a long if-else chain to identify the first word of the command, a design that is markedly inferior to having a dictionary of command objects, each knowing its own name and (for example) able to describe itself with a help text.

Question 13: PlayDiceGame