Oxford Cambridge and RSA Examinations
GCE
Computer Science
H446/02: Algorithms and programming
Advanced GCE
Mark Scheme for November 2020Oxford Cambridge and RSA Examinations
OCR (Oxford Cambridge and RSA) is a lea
...
Oxford Cambridge and RSA Examinations
GCE
Computer Science
H446/02: Algorithms and programming
Advanced GCE
Mark Scheme for November 2020Oxford Cambridge and RSA Examinations
OCR (Oxford Cambridge and RSA) is a leading UK awarding body, providing a wide range of
qualifications to meet the needs of candidates of all ages and abilities. OCR qualifications
include AS/A Levels, Diplomas, GCSEs, Cambridge Nationals, Cambridge Technicals,
Functional Skills, Key Skills, Entry Level qualifications, NVQs and vocational qualifications in
areas such as IT, business, languages, teaching/training, administration and secretarial skills.
It is also responsible for developing new specifications to meet national requirements and the
needs of students and teachers. OCR is a not-for-profit organisation; any surplus made is
invested back into the establishment to help towards the development of qualifications and
support, which keep pace with the changing needs of today’s society.
This mark scheme is published as an aid to teachers and students, to indicate the requirements
of the examination. It shows the basis on which marks were awarded by examiners. It does not
indicate the details of the discussions which took place at an examiners’ meeting before marking
commenced.
All examiners are instructed that alternative correct answers and unexpected approaches in
candidates’ scripts must be given marks that fairly reflect the relevant knowledge and skills
demonstrated.
Mark schemes should be read in conjunction with the published question papers and the report
on the examination.
© OCR 2020H446/02 Mark Scheme November 2020
2
Annotations
Annotation Meaning
Omission mark
Benefit of the doubt
Subordinate clause / consequential error
Incorrect point
Expansion of a point
Follow through
Not answered question
No benefit of doubt given
Point being made
Repeat
Correct point
Too vague
Zero (big)
Blank Page – this annotation must be used on all blank pages within an answer
booklet (structured or unstructured) and on each page of an additional object
where there is no candidate response.H446/02 Mark Scheme November 2020
Level 1
Level 2
Level 3H446/02 Mark Scheme November 2020
4
Question Answer Marks Guidance
1a
1 mark for definition
• Removal of unnecessary detail // Simplification to allow development of a
program more easily
1 mark to max 2 for application
e.g.
• The actual movements are represented by vertices/lines
• State of the move is represented by a letter/symbol rather than the actual
move position
• Tree does not show details about what the moves are
3
AO1.1
(1)
AO2.1
(1)
AO2.2
(1)
Allow other suitable examples that
are relevant to the scenario in the
question.
1b One node (node A) has more than 2 connections
Nodes aren’t ordered (e.g. F is C’s left child)
1
AO2.1
(1)
1c 1 mark for identification
• Null pointers
1
AO2.1
(1)
1d
1 mark per bullet
• Take A as starting node
• Visit B, C and E
• Visit D, F, G and H
• Visit I and J
4
AO1.2
(2)
AO2.2
(2)
Allow the reverse ordering from
right to left e.g. A; E, C, B; H, G, F,
D; J, I
1ei
1 mark per bullet to max 3
• Search the tree to find the location of Node E // by example of search
• Replace the content of node E with blank/null/equivalent
• Make node A point to the node H
• Add node E to the empty node list
3
AO1.2
(3)
1eii
1 mark per bullet to max 3
• Search the tree to find the location of node G // by example of search
• Create a new node with value K
• Add a pointer from node G to the new node
• Make node K point to null/equivalent
3
AO1.2
(3)H446/02 Mark Scheme November 2020
1f
1 mark per similarity to max 2
• Both consists of nodes
• Both are connected by edges/links
• Both are non-linear data structures
• Both are dynamic data structures
1 mark per difference to max 2
• Tree is 1-directional whereas a graph is 2-directional
• Tree has a root node whereas a graph does not have a (clear) root node
• Tree will not have cycles whereas graphs can contain cycles
• Tree will not be weighted whereas edges in a graph can be weighted
4
AO1.1
(4)
2a
1 mark per bullet to max 4
e.g.
• Decomposition splits the problem into smaller sub problems
• Repeated decomposition gives solvable parts
• The division can lead to the development of subroutines/modules
• The division can lead to a logical division between programmers/teams
• ...e.g. one team works on one section and another concurrently on another
4
AO1.1
(2)
AO1.2
(2)H446/02 Mark Scheme November 2020
6
2b
Mark Band 3 – High level (7-9 marks)
The candidate demonstrates a thorough knowledge and understanding of
concurrent processing; the material is generally accurate and detailed.
The candidate is able to apply their knowledge and understanding directly and
consistently to the context provided. Evidence/examples will be explicitly
relevant to the explanation.
There is a well-developed line of reasoning which is clear and logically
structured. The information presented is relevant and substantiated.
Mark Band 2 – Mid level (4-6 marks)
The candidate demonstrates reasonable knowledge and understanding of
concurrent processing; the material is generally accurate but at times
underdeveloped.
The candidate is able to apply their knowledge and understanding directly to
the context provided although one or two opportunities are missed.
Evidence/examples are for the most part implicitly relevant to the explanation.
The candidate provides a reasonable discussion, the majority of which is
focused. Evaluative comments are, for the most part appropriate, although one
or two opportunities for development are missed.
There is a line of reasoning presented with some structure. The information
presented is in the most part relevant and supported by some evidence.
Mark Band 1 – Low Level (1-3 marks)
The candidate demonstrates a basic knowledge of concurrent processing with
limited understanding shown; the material is basic and contains some
inaccuracies. The candidates makes a limited attempt to apply acquired
knowledge and understanding to the context provided.
The candidate provides a limited discussion which is narrow in focus.
Judgements if made are weak and unsubstantiated.
The information is basic and comunicated in an unstructured way. The
information is supported by limited evidence and the relationship to the
evidence may not be clear.
0 marks
No attempt to answer the question or response is not worthy of credit.
9
AO1.1
(2)
AO1.2
(2)
AO2.1
(2)
AO3.3
(3)
AO1: Knowledge and Understanding
Indicative content
• Processes are happening at the
same time/at overlapping times
• One process may need to start
before a second has finished
• Individual processes are threads,
each thread has a life line
• One request will be sent to the
server, this will have a thread
AO2: Application
• Multiple requests to the server can
be made at the same time
• Programming on server will need
to allow multiple threads to
manipulate a list of requests
• Programming will need to restrict
access to the database of
seats/sales etc.
• Will allow those reading and writing
to manipulate at the same time
• Record locking will need
implementing – more complex
programming
• May be selling alongside other
systems, therefore needs to
communicate with external
systems that will also use record
locking to avoid two different
external companies accessing and
selling the same tickets.
AO3: Evaluation
• Will allow for multiple access to the
website at the same time by
different customers – as it would
happen in real lifeH446/02 Mark Scheme November 2020
• Will allow for multiple ticket sales
for the same event without selling
the same seat twice
3a
1 mark per bullet
• Calculation of result to 3
• Call with thisFunction(theArray, num1=4, num2=7, num3=35)
• Result = 5
• call with thisFunction(theArray,num1=6,num2=7,num3=35)
• (Result = 6) return of value 6
Function call num1 num2 num3 result
thisFunction(theArray,0,7,35) 0 7 35 3
thisFunction(theArray,4,7,35) 4 7 35 5
thisFunction(thisArray,6,7,35) 6 7 35 6
5
AO2.1
(3)
AO2.2
(2)
3b Binary search
1
AO2.1
(1)
3c
1 mark per bullet to max 4, e.g.
• Recursion uses more memory…
• …iteration uses less memory
• Recursion declares new variables //variables are put onto the stack each
time…
• ...iteration reuses the same variables
• Recursive can run out of memory/stack space…
• …while iteration cannot run out of memory
• Recursion can express a problem more elegantly // in fewer lines of code…
• …while iteration can take more lines of code // be harder to understand
• Recursion will be self-referential // will call itself…
• … whereas iteration does not
4
AO1.1
(2)
AO1.2
(2)H446/02 Mark Scheme November 2020
8
3d
1 mark per bullet to max 6
• Retains function call
• Uses a loop
• …that will loop until all elements inspected or value found
• Updates num1 appropriately
• Updates num2 appropriately
• Returns -1 in the correct place if the value has not been found
• Returns the result in the correct place if the value has been found
e.g.
function thisFunction(theArray, num1, num2, num3)
while (true)
result = num1 + ((num2 - num1) DIV 2)
if num2 < num1 then
return -1
else
if theArray[result] < num3 then
num1 = result + 1
elseif theArray[result] > num3 then
num2 = result - 1
else
return result
endif
endif
endwhile
endfunction
6
AO2.2
(3)
AO3.1
(3)H446/02 Mark Scheme November 2020
4a
1 mark per bullet
• By reference will change the actual contents of the array in the main program//
when control returns to the main program the array will be sorted
• By value would create a copy and not change the original // when control
returns to the main program the array will not be sorted
• By value the array is local to the function.
• By reference will use less memory
2
AO1.2
(1)
AO2.2
(1)
4b
1 mark pet bullet to max 3
• Descending order
• Line 07 (dataArray[tempos] queueTail then
return null
else
queueHead = queueHead + 1
return buffer[queueHead-1]
endif
endfunction
5
AO2.2
(2)
AO3.3
(3) Note: Accept alternative valid
underlying implementation answers
e.g. Shifting all elements in queue
forward.
5cii
1 mark per bullet to max 6
• Function declaration taking parameter
• Checking if queue is full
• …returning -1
• (Otherwise) incrementing queueTail
• Adding newJob to buffer(queueTail)
• Returning 1
e.g.
function enqueue(newJob)
if queueTail == 99 then
return -1
else
queueTail = queueTail + 1
buffer[queueTail] = newJob
return 1
endif
endfunction
6
AO2.2
(3)
AO3.3
(3)H446/02 Mark Scheme November 2020
5ciii
1 mark per bullet to max 8
• Inputting user choice
• If enqueue chosen input job name
• …call enqueue with input value as parameter
• …check if return value is -1 and output full
• …otherwise output message that item is added
• If dequeue chosen
• …call dequeue and save returned value
• …output returned value (jobname) if not null
• …or output queue is empty
e.g.
main()
choice = input("Add or remove?")
if choice == "ADD" then
jobname = input("Enter job name")
returnValue = enqueue(jobname)
if returnValue == -1 then
print("Queue full")
else
print("Job added")
endif
else
returnValue = dequeue()
if returnValue == null then
print("Queue empty")
else
output returnValue
endif
endif
endmain
8
AO2.2
(2)
AO3.3
(6)
Allow equivalent checks / logic
5d
1 mark per bullet to 3
• Check if either head or tail are incremented to above 99
• … set to be 0 instead
• When checking if array is full check if (queueTail == queueHead – 1) OR
(queueTail==99 AND queueHead==0)
3
AO2.1
(1)
AO2.2
(2)
Credit equivalent modulo arithmetic
solutionH446/02 Mark Scheme November 2020
16
5e
1 mark per bullet to max 3, e.g.
• Use a different structure e.g. a linked list
• …items can be added at different points in the linked list depending on priority
• …by changing the pointers to items needing priority
• Have different queues for different priorities
• …add the job to the queue relevant to its priority
• …print all the jobs in the highest priority queue first
3
AO2.1
(2)
AO2.1
(1)
Allow other suitable descriptions
that show how the program could
be amended.
6ai
1 mark per bullet
• Points to where the next/first free node is
• To add data into the linked listed.
2
AO1.2
(1)
AO2.2
(1)
6aii Points to the first element in the linked list AO11.2
(1)H446/02 Mark Scheme November 2020
6aiii
1 mark per bullet
• No change made to nodes/pointers unaffected by this removal
• Index 0 points to 2 instead of 3
• Node 9 points to 3 instead of -1 // Node freeListPointer points to 3 instead of 4
• Node 3 points to 4 // -1 (must match MP3
Solution:
index data pointer
headPointer 0 0 2.6 2
1 3.5 -1
freeListPointer 4 2 1.8 1
3 6.9 -1
4 5
5 6
6 7
7 8
8 9
9 3
Alternative Solution:
index data pointer
headPointer 0 0 2.6 2
1 3.5 -1
freeListPointer 3 2 1.8 1
3 6.9 4
4 5
5 6
6 7
7 8
8 9
9 -1
4
AO1.2
(1)
AO2.2
(1)
6.9 3 may or may not be written by
candidates, both are acceptable.
Candidates may add the node
freed up (node 3) to the start or
the end of the free storage. Award
marks for both approaches.H446/02 Mark Scheme November 2020
18
6bi
1 mark per bullet
• Class declaration and all code is nested within the class
• Two private identifiers data and pointer (with suitable data types if given)
• Public constructor heading as a procedure (public may be implied but cannot
be private) taking both parameters as given in table
• Assigns parameters to the attributes
e.g.
public class node
private data as real
private pointer as integer
public procedure new(newData, newPointer)
data = newData
pointer = newPointer
endprocedure
endclass
4
AO2.2
(1)
AO3.3
(3)
Accept
public node(newData, newPointer)
(may also have data stypes for
parameters e.g. int newData)
Accept:
this.data = newData
this.pointer = newPointer
or similar
6bii
1 mark per bullet to max 2
• A get method allows the attribute to be accessed / returned
• A set method allows the attribute to be changed (with parameters)
2
AO2.2
(2)
6c
1 mark per bullet to max 6
• Initialise message string
• Start with the headPointer
• Check if the headPointer is null
• …return that the list is empty
• Check the pointer of the node at headPointer
• If it is not null/-1/the last element
• loop through all the linkedList elements
• …concatenate the pointer to the message
• …replacing the pointer with the current node’s pointer each time
• …if the data is found concatenate the pointer and “found” to the message
and return it
• …if the loop ends and the data item is not found, concatenate “not found” to
the message and return it
6
AO1.2
(2)
AO2.1
(2)
AO2.2
(2)H446/02 Mark Scheme November 2020
6di
1 mark for identifying error and correction (identification may be implicit)
• Line 02 tempPointer should become headPointer, not -1
tempPointer = headPointer
• Line 05 message should say it’s empty not full
print("List is empty")
• Line 07 pointer should be tempPointer
while linkedList[tempPointer].getPointer() != -1
• Line 08 Incorrect call to node pointer dataToPrint = dataToPrint + “
” + linkedList[tempPointer].getData()
• Line 09 assignment is wrong way
tempPointer = linkedList[tempPointer].getPointer()
• Line 11 missing final parenthesis print(dataToPrint+ “ ” +
linkedList[tempPointer].getData())
3
AO2.1
(2)
AO2.2
(2)
Do not award marks for stating
the line number without a valid
correction.
6dii
1 mark per bullet
• Stepping Through The Code…
• …to run one line at a time to see where the error is
• Syntax Error Highlighting….
• ….to distinguish syntax errors in the program code
• Setting breakpoints…
• ….to debug individual sections of code at a time
• Variable watch window…
• …To check that the variables are being updated corrected
6
The features must relate to
debugging code.
Allow other suitable features
appropriate to debugging code.
1 Mark for identification and 1
mark for suitable expansion.H446/02 Mark Scheme November 2020
20
6e
Mark Band 3 – High level (9-12 marks)
The candidate demonstrates a thorough knowledge and understanding of
the object orientied techniques; the material is generally accurate and
detailed. The candidate is able to apply their knowledge and understanding
directly and consistently to the context provided.
Evidence/examples will be explicitly relevant to the explanation.The
candidate is able to weigh up the use of all of the object orientied
techniques which results in a supported and realistic judgment as to
whether it is possible to use them in this context.
There is a well-developed line of reasoning which is clear and logically
structured. The information presented is relevant and substantiated.
Mark Band 2 – Mid level (5-8 marks)
The candidate demonstrates reasonable knowledge and understanding of
the object orientied techniques; the material is generally accurate but at
times underdeveloped.
The candidate is able to apply their knowledge and understanding directly
to the context provided although one or two opportunities are missed.
Evidence/examples are for the most part implicitly relevant to the
explanation. The candidate makes a reasonable attempt to come to a
conclusion showing some recognition of influencing factors that would
determine whether it is possible to use each object orientied technique in
this context.
There is a line of reasoning presented with some structure. The
information presented is in the most part relevant and supported by some
evidence
Mark Band 1 – Low Level (1-4 marks)
The candidate demonstrates a basic knowledge of the object orientied
techniques with limited understanding shown; the material is basic and
contains some inaccuracies. The candidates makes a limited attempt to
apply acquired knowledge and understanding to the context provided.
The candidate provides nothing more than an unsupported assertion.
The information is basic and comunicated in an unstructured way. The
information is supported by limited evidence and the relationship to the
evidence may not be clear.
12
AO1.1 (3)
AO1.2 (3)
AO2.1 (3)
AO3.3 (3)
AO1: Knowledge and Understanding
Indicative content
• Classes, this a template. It will define what
attributes and methods an object should have.
• Objects, when you create an instance of a class.
Each object that is instantiated from the same
class will share the same attributes and methods.
• Inheritance, when a sub class takes on the
attributes and methods from a superclass/parent
class. It can also have its own extra
attributes/methods.
• Overriding, when a method name is the same in a
parent and sub class, then the method in the
parent/super class will be overridden
• Encapsulation, this protects attributes of an object
by making them private so that they can’t be
accessed or altered accidentally by other objects.
AO2: Application
• A class can be used to declare the attributes and
methods for the linked list. These will initialise the
nodes and join them.
• Objects can then be used be used to instantiate
the class each time a new linked list is needed.
Each can be given a different identifier by the
other programs.
• Further subclasses may be used by other
programs. These can therefore take on the
attributes and methods from the base class.
These can also be changed or overridden
depending on the purpose of the other programs.
• Encapsulation can be used by using set and get
methods to ensure that the nodes in the linked list
are changed in a way that is intended.
AO3: EvaluationH446/02 Mark Scheme November 2020
0 marks
No attempt to answer the question or response is not worthy of credit.
• Use of OPP techniques will allow for code
reusability. His linked list can be saved as library
and then reused many times leading to less code.
• OOP also allows programs to be easier to modify
and maintain.OCR (Oxford Cambridge and RSA Examinations)
The Triangle Building
Shaftesbury Road
Cambridge
CB2 8EA
[Show More]
