Total marks available: 120, or 30 per question. First-class borderline: 80-ish; pass-fail borderline: 40-ish; but these marks get shifted up or down by normalisation, based on the extent to which this was a hard/easy paper judging from its effects on students, esp. near the borderlines.
Assertion:
throughout the computation, p >= q.
... Proof:
p and q are initially equal;
but whenever they are equal, n = r > 0, and so the
next step is to increase p;
so q can never overtake p.
Assertion:
if the computation does't terminate, then p eventually
takes every possible [positive, odd] value.
... Proof:
Every time round the loop, either p or q increases
to the next odd value;
but q never exceeds p, so p must eventually
reach any chosen value [it can't get `stuck', for then q
would eventually overtake it].
Now consider what happens when first p = r+2.
[Must happen, by the second assertion, and since r
is odd]
As p has just been incremented, q is at most
r [by the first assertion];
if it is equal to this value, then
n = r - k² + l² =
r - (p-q)(p+q-2)/4 = 0,
and the computation terminates;
if less, then, by the same analysis, n < 0 [as
l is smaller], so the next step is to increase q.
So q will eventually reach the value r, and
the computation will halt.
So the computation cannot continue indefinitely, and must therefore halt. When it does so, the above analysis shows that (p-q)/2 and (p+q-2)/2 are factors of r, as required. [8 marks for getting the essentials of this argument, a further 6 for filling in enough detail to be convincing]
If r is negative, then the roles of p and q
in the above are interchanged;
the code will still terminate and find [the same] factors [with
one of them negative]. [3 marks]
In the case where r is even, the code can fail to
terminate [for example, 2 cannot be written as the difference
of two (integer) squares, so the code cannot terminate in this case].
[3 marks. Bonus for saying when it could terminate (when
r is a multiple of 4, large bonus for proving that it indeed
does terminate in every such case.]
Extra comments: From the examples, we see that there are two phases: in the first, trivial, phase, we repeatedly find n > 0, so increase p until k [in the above terms] is just greater than the square root of r [if r is a perfect square, then this phase will terminate the calculation, with finally k equal to its square root and l still zero]. After this phase, n stays reasonably small, clearly never more than q [as it was negative before we added], and never less than -p [as it was positive before we subtracted]. As it stands, this is an impractical way of factorising -- though note that it does no multiplication or division! -- but phase one can be short-circuited by starting with k the integer part of the square root of r, then in the early stages of phase two we can `guess' how much we can increment q before we have to increment p again, and the later stages (when p-q is small) can be avoided by looking for small factors of r separately. With lots of refinements, this becomes a practicable way of helping to factorise large numbers [though not as good as the best available ways, which use deep results in number theory].
You shouldn't aim to reproduce lecture notes exactly, but to capture the essence. For example, you might start: `The DNF problem is to arrange an array of red, white and blue pebbles into order, reds then whites then blues. This can be done by imagining the array partitioned into four sections, (in order) red, white, unsorted and blue -- see the diagram -- and the task is to select one of the unsorted pebbles, determine its color and adjust the partitions accordingly. Initially, the red, white and blue partitions are empty, and the algorithm terminates when the unsorted partition blah, blah, ...'.Marks: description of DNF problem -- 5; of algorithm -- 10; explanation of QS in terms of DNF -- 7; comments on efficiency -- 3; steps to improve it -- 5; total 30.
Following the hint, consider the case k=2. In this case, basically the roads in a BDST subset define a unique path `through' each village -- in each village, you can only go either back the way you came or out on the `other' road. Following this path from one end to the other must, if the villages are connected, result in a journey through all the villages. This suggests a transformation from Hamiltonian Circuit [HC]. One way round, this is trivial; if there is a HC, then the roads in it constitute a solution to the BDST problem of the same set of roads and villages and with k=2. [6 marks if you get this far]
Sadly, the other way round is much harder, as we don't necessarily get back to the village we started at, so a `no' answer to HC doesn't mean that the identical BDST problem [with k=2] also has a `no' answer. [3 marks for realising this] So we have to tweak things a little.
There are several ways of doing this. Here is the simplest. Take an arbitrary village, say A, and duplicate it; that it, build a new village A', and connect it to all the places that A is connected to. Now connect A and A' to new villages X and X', respectively. This new network has a Hamiltonian path, starting at X, going round all the villages, and finishing at X', if and only if the original network had a Hamiltonian circuit; for the circuits [which could, of course, be started anywhere] A, B, C, ..., Z, A are in direct correspondence with the paths X, A, B, C, ..., Z, A', X' [which can only start or finish at X, X', for these are connected only to A, A']. So, the original network has a HC if and only if the new network, which can clearly be constructed in polynomial time, has a BDST with k=2. [9 marks. Part credit for any sensible attempt, full credit for anything which could easily be patched up into a correct solution.]
So, any given instance of HC can be transformed in polynomial time into a polynomial number of instances of BDST. [4 marks] Since HC is NP-complete, so must be BDST. [4 marks] QED. [And we have proved incidentally that the Hamiltonian Path problem is NP-complete.]
... b b b b 0 1 0 1 1 Y Y X Y Y X Y Y X Y Y b b ...where b represents blanks, 0, 1 represent the binary number thus far, and Y represents a crossed-out X. Starting from the right, we scan left, crossing out alternate X's, until we reach a blank, which we replace by a 0 if we have found an even number of X's and by a 1 if an odd number. Then scan back to the right-hand blank, halting if we don't find an X. The number of X's halves each time, so always corresponds to the more-significant part of the binary number which is yet to be written. [15 marks for this, or any acceptable proposed stratagem, including awareness of the problem, tape layout, etc.]
In more detail, we have:
State 0: [Scan left, we've read an even number of X's.]
If the symbol read is blank, write 0, enter state 2, and
move right.
If it's X, write Y, enter state 1 and move left.
Otherwise, write the symbol back, stay in state 0, and move left.
State 1: [Scan left, we've read an odd number of X's.]
If the symbol read is blank, write 1, enter state 2, and
move right.
If it's X, write X, enter state 0 and move left.
Otherwise, write the symbol back, stay in state 1, and move left.
State 2: [Scan right, no X yet seen]
If we read an X, enter state 3 and move right,
on blank, halt;
on any other symbol, write it back and move right.
State 3: [Scan right, X has been seen]
On blank, write it back, enter state 0 and move left.
On any other symbol, write it back, stay in state 3, and move right.
[10 marks for this, or any other equivalent description, and
another 5 for accuracy in the detail.
A matrix formulation would be equally acceptable, as long as you
also gave a general description of what the states signified.]
G12FCO home page.
Mock Exam .