AQA A level Computer Science Paper 1 Unofficial Mark Scheme

I think that the
'how many out of 4 algorithms'
was only three because one of them was a recursive algorithm
which would therefore have been exponential, and therefore intractable

also the stack error, should be a stack underflow

Guys what did I get for the binary tree?

Did u get Judith , then Caspar, then false as output ?


Posted from TSR Mobile

No because O is less than N (for Norbert root node) so u branch left to Judith


Posted from TSR Mobile

I put all 4 for the tractable problem question.

I thought that the theory was relatively easy, but VERY wordy. Spent a lot of my time trying to read over it.

The practical task (especially the last task) was very difficult.

I think that the
'how many out of 4 algorithms'
was only three because one of them was a recursive algorithm
which would therefore have been exponential, and therefore intractable

* Does this class diagram use inheritance (No), protected attributes (No), something else (Yes).

I also got this, unsure if it was right. Wasn't the class only showing composition?

For the last part of section D where you had to figure out whether a fox had to cross the river to eat, it said make a new subroutine but I made a function return a True or False value as to whether it can eat the rabbits or not.

Is that going to be ok? It worked properly

Okay so here is what I can remember of the questions and my answers:

Section A
Question 1: Syntax diagram / BNF
* Are these three inputs valid? Yes; No; Yes.
* Define the natural symbol: <natural> ::= <digit> | <digit><natural>
[Alternate]

Question 2: Finite state machines
* This state is where invalid strings end up in.
* This is the accepting state, so strings here are valid formats for a postcode.
* Regex: "/a /a? /d (/d | /a)? /d /a /a" [Alternate answer would be (/d? | /a?) in the brackets]

Question ?: Time complexity
* Which algorithm runs in O(n log n) time? Merge sort.
* Which of these four algorithms are used to solve tractable problems? All 4.
* What is the time complexity of a bubble sort? O(n^2).
* Why? Each pass puts the largest number at the end (with ascending order). Worst case is the algorithm requires (n - 1) passes [largest n-1 numbers at end and first must be smallest]; each pass requires (n - 1) comparisons, and (n - 1)(n - 1) is asymptotic to n^2 for large n.

Question ?:
* How is a stack suitable for software which has the actions 'undo' and 'repeat'? Stack uses LIFO; can use peek for repeat and pop then peek for undo.
* What is the name for the error when the user enters 'repeat' but the stack is empty? Stack underflow according to others (though I put runtime error).

Question ?: TreeSearch pseudocode
* What is a recursive subroutine? A subroutine which calls itself.
* Trace table for this call. Unsure whether my answer is right, but my table contained (left to right, top to bottom): TreeSearch(Olivia, Norbert) | "Searched Norbert" | TreeSearch(Olivia, name beginning with P) | "Searched P" | return False in both calls".

Question ?: Vectors
* What is a heuristic and how does it apply to this maze game? A heuristic is an algorithm which essentially uses educated guesses - it tries to find a sufficiently accurate solution (which may not be the optimal one) in a reasonable amount of time.
* Dot product - Unsure of vectors but I think they were [5, 3] and [1, -1] or similar so answer would be 5 - 3 = 2.
* Add [5, 2] and [3, 1]. Answer: [8, 3].
* Carry this trace table out (v = [6, -4]; dot product = 2; True).

Section B
Write a program which does run length encoding.
My method: use a 'for' loop to run through the string input by the user; if it is the same as the previous character, increment a counter by one; if it is different, add the previous character / value pair to the output string and reset the counter.

Section C
* Does this class diagram use inheritance (No), protected attributes (No), private attributes (Yes). ['Attributes' may have been 'methods' for one or two of the last parts.]
* Name a subclass (Rabbit or Fox).
* What is the difference between 'protected' and 'private'? Private can only be accessed in the class itself; protected can also be accessed in subclasses.

Section D
Question 9: Validation for InputCoordinates. Method: use a while/dowhile loop until the co-ordinate is between 0 and (LandscapeSize - 1) inclusive.
Question 10: Make an overriden function in Rabbit so that ProbabilityOfDeathOtherCauses increase with age (*1.5 multiplier for males; +0.05 addition for females at least 2 time periods old).
Question 11: Add a river to the simulation.
Question 12: Check if the fox's path would cross the river. My method: check if the fox and rabbit are on opposite sides of the river with the following logic - if (FoxX < 5 and RabbitX > 5) or (FoxX > 5 and RabbitX < 5) or (FoxY < 2 and RabbitY > 2) or (FoxY > 2 and RabbitY < 2), return false (river is in the path); else return true.

No because O is less than N (for Norbert root node) so u branch left to Judith


Posted from TSR Mobile

This is wrong, O is greater than N (L M N ... O) so you should have branched to the right and checked it vs phil next.

I think that the
'how many out of 4 algorithms'
was only three because one of them was a recursive algorithm
which would therefore have been exponential, and therefore intractable

Which one was recursive? i cant remember the list of algorithms

I think that the
'how many out of 4 algorithms'
was only three because one of them was a recursive algorithm
which would therefore have been exponential, and therefore intractable

Recursive algorithms are not necessarily exponential - in fact, most (all?) recursive algorithms can be implemented instead using for loops. For example, with a bubble sort you could use recursion, or a nested for loop, but either way it's O(n^2).


Indeed the diagram did only have composition (filled in diamonds).