19.1 Algorithms (A Level)

A Level · 7 questions found

What this topic covers

Linear search: write algorithm, conditions, performance
Binary search: write algorithm, required conditions, performance vs data size
Insertion sort and bubble sort: write algorithms; performance depends on data order and size
Full ADTs — find, insert, delete in: stack, queue, linked list, dictionary, binary tree
Graph as ADT: key features; A* and Dijkstra’s algorithms for searches
Implementing ADTs from other ADTs
Compare algorithms: Big O notation for time and space complexity

Past paper questions

May/Jun 2024 Paper 3 v2 8 marks

Show mark scheme

8(a) [4 marks]

mark for each correctly completed line (
Max 4
)
DECLARE Widgets : ARRAY[1:50000] OF STRING
DECLARE TopOfList : INTEGER
DECLARE EndOfList : INTEGER
DECLARE Count : INTEGER
DECLARE ToFind : STRING
DECLARE Found : BOOLEAN
DECLARE NotInList : BOOLEAN
TopOfList

1
EndOfList

50000
OUTPUT "Enter the name of the item you wish to find "
INPUT ToFind
Found

FALSE
NotInList

FALSE
Count

TopOfList
WHILE
Found = FALSE
AND
NotInList = FALSE
//
Count <= EndOfList
IF
ToFind = Widgets[Count]
//
Widgets[Count] = ToFind
THEN
Found

TRUE
ENDIF
Count

Count + 1
IF
Found = FALSE AND Count > EndOfList
THEN
NotInList

TRUE
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Item found at position ", Count - 1, " in array"
OUTPUT "Item not in array"
ENDIF

8(b) [4 marks]

mark per mark point (
Max 3
)
Linear search sequentially checks each element of the array / list.
… until the matching element is found, or the end of the array / list is reached.
Binary search finds the mid-point of an array/list
and
determines which side contains the item to be found
… it discards the half of the array/list not containing the search item // … it finds the position of a target value within
an array / list by repeatedly halving the target search field.
The binary search requires the elements to be sorted // The linear search does not require the elements to be
sorted.
The binary search will usually do many fewer comparisons of records/iterations against the target than a linear
search before it finds its target.
Linear search starts at the beginning of the array/list
and
binary search starts in the middle of the array/list.
mark per mark point (
Max 2
)
Big O for binary search is O (Log
2
n)
Big O for linear search is O (n)
Big O notation is used to indicate the time / space complexity of an algorithm

May/Jun 2024 Paper 4 v1 12 marks

1 A program needs to take integer numbers as input, sort the numbers and then search for a specific number. (a) The integer numbers will be stored in the global 1D array, DataStored, with space for up to 20 integers. The global variable NumberItems stores the quantity of items the array contains. Write program code to declare DataStored and NumberItems. Save your program as Question1_J24. Copy and paste the program code into part 1(a) in the evidence document. [1] (b) The procedure Initialise(): • prompts the user to input the quantity of numbers the user would like to enter • reads the input and validates it is between 1 and 20 (inclusive) • prompts the user to input each number and stores each number in DataStored. Write program code for Initialise(). Save your program. Copy and paste the program code into part 1(b) in the evidence document. [5] (c) The main program stores 0 in NumberItems, calls Initialise() and then outputs the contents of DataStored. (i) Write program code for the main program. Save your program. Copy and paste the program code into part 1(c)(i) in the evidence document. [2] (ii) Test your program by inputting the following data in the order given: 30 5 3 9 4 1 2 Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 1(c)(ii) in the evidence document. [2] (d) The procedure BubbleSort() uses a bubble sort to sort the data in DataStored into ascending numerical order. (i) Write program code for BubbleSort(). Save your program. Copy and paste the program code into part 1(d)(i) in the evidence document. [4] (ii) Write program code to amend the main program to call BubbleSort() and then output the contents of DataStored. Save your program. Copy and paste the program code into part 1(d)(ii) in the evidence document. [1] (iii) Test your program by inputting the following data in the order given: 5 3 9 4 1 2 Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 1(d)(iii) in the evidence document. [1] (e) The function BinarySearch(): • takes the integer parameter DataToFind to search for in the array • performs an iterative binary search on the array DataStored • returns the index where DataToFind is found in DataStored. If DataToFind is not found, the function returns −1. (i) Write program code for the iterative function BinarySearch(). Save your program. Copy and paste the program code into part 1(e)(i) in the evidence document. [6] (ii) Write program code to amend the main program to: • take a number as input from the user • call BinarySearch() with the number input • output the value returned from the function call as its parameter. Save your program. Copy and paste the program code into part 1(e)(ii) in the evidence document. [3] (iii) Test your program twice with the following inputs: Test 1: 5 1 6 2 8 10 2 Test 2: 5 1 6 2 8 10 7 Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 1(e)(iii) in the evidence document. [2]

Show mark scheme

1(a) [1 mark]

1 mark for:
Declaration of (global) array with identifier
DataStored
(Integer and 20 spaces)
and
NumberItems
(Integer)
public static Integer[] DataStored = new Integer[20];
public static Integer NumberItems= 0;
VB.NET
Dim DataStored(19) As Integer
Dim NumberStored As Integer = 0
Python
global DataStored #integer
global NumberItems #Integer 20 items

1(b)

Python
def Initialise():
global DataStored
global NumberItems
Valid = False
while(Valid == False):
NumberItems = int(input("How many numbers will you enter?")) #loop until < 20
if NumberItems > 0 and NumberItems< 21:
Valid = True
for Count in range(0, NumberItems):
DataStored.append(int(input("Enter number")))

1(c)(i) [2 marks]

1 mark each:
Storing
0
in
NumberItems
and
then calling
Initialise()
Outputting all contents of array
DataStored
public static Integer NumberItems= 0;
Initialise();
for(Integer X = 0; X < NumberItems; X++){
System.out.println(DataStored[X]);
VB.NET
NumberItems = 0
Initialise()
For X = 0 To NumberItems - 1
Console.WriteLine(DataStored(X))
Python
NumberItems = 0
Initialise()
print(DataStored)

1(c)(ii) [2 marks]

1 mark each
Output showing quantity entered twice (30 and 5) with first being invalid
Array output 3 9 4 1 2

1(d)(i)

Python
def BubbleSort():
global DataStored
global NumberItems
for Count in range(0, NumberItems):
for Count2 in range(0, NumberItems-1):
if DataStored[Count2] > DataStored[Count]:
DataStored[Count2], DataStored[Count] = DataStored[Count],
DataStored[Count2]

1(d)(ii) [1 mark]

1 mark for calling
BubbleSort()
and
outputting array contents after
VB.NET
BubbleSort()
For X = 0 To NumberStored - 1
Console.WriteLine(DataStored(X))
e.g. Java
BubbleSort();
for(Integer X = 0; X < NumberItems; X++){
System.out.println(DataStored[X]);
e.g. Python
BubbleSort()
print(DataStored)

1(d)(iii) [1 mark]

1 mark for screenshot showing the inputs and the values in the correct order

1(e)(i)

VB.NET
Function BinarySearch(DataToFind)
Dim First As Integer = 0
Dim Last As Integer = NumberItems
Dim MidValue As Integer
While (First <= Last)
MidValue = (First + Last) / 2
If DataToFind = DataStored(MidValue) Then
Return MidValue
End If
If DataToFind < DataStored(MidValue) Then
Last = MidValue - 1
Else
First = MidValue + 1
End If
End While
Return -1
End Function
Python
def BinarySearch(DataToFind):
global DataStored
global NumberItems
First = 0
Last= NumberItems
while(First <= Last):
MidValue = int((First + Last) / 2)
if DataToFind == DataStored[MidValue]:
return MidValue
if DataToFind < DataStored[MidValue]:
Last = MidValue - 1
else:
First = MidValue + 1
return -1

1(e)(ii) [3 marks]

1 mark each:
Taking number as input
… calling
BinarySearch
with input
Outputting value returned
Scanner scanner = new Scanner(System.in);
System.out.println("Enter a number to find");
Integer Search = Integer.parseInt(scanner.nextLine());
System.out.println(BinarySearch(Search));
VB.NET
Console.WriteLine("Enter a number to find")
Dim Search As Integer = Console.ReadLine()
Console.WriteLine(BinarySearch(Search))
Python
Search = int(input("Enter a number to find"))
print(BinarySearch(Search))

1(e)(iii) [2 marks]

1 mark for each test
Test 1 – Accept found in index 16

May/Jun 2024 Paper 4 v1 3 marks

3 A program reads data from the user and stores the data that is valid in a linear queue. The queue is stored as a global 1D array, QueueData, of string values. The array needs space for 20 elements. The global variable QueueHead stores the index of the first element in the queue. The global variable QueueTail stores the index of the last element in the queue. (a) The main program initialises all the elements in QueueData to a suitable null value, QueueHead to −1 and QueueTail to −1. Write program code for the main program. Save your program as Question3_J24. Copy and paste the program code into part 3(a) in the evidence document. [1] (b) The function Enqueue() takes the data to insert into the queue as a parameter. If the queue is not full, it inserts the parameter in the queue, updates the appropriate pointer(s) and returns TRUE. If the queue is full, it returns FALSE. Write program code for Enqueue(). Save your program. Copy and paste the program code into part 3(b) in the evidence document. [4] (c) The function Dequeue() returns "false" if the queue is empty. If the queue is not empty, it returns the next item in the queue and updates the appropriate pointer(s). Write program code for Dequeue(). Save your program. Copy and paste the program code into part 3(c) in the evidence document. [3] (d) The string values to be stored in the queue are 7 characters long. The first 6 characters are digits and the 7th character is a check digit. The check digit is calculated from the first 6 digits using this algorithm: • multiply the digits in position 0, position 2 and position 4 by 1 • multiply the digits in position 1, position 3 and position 5 by 3 • calculate the sum of the products (add together the results from all of the multiplications) • divide the sum of the products by 10 and round the result down to the nearest integer to get the check digit • if the check digit equals 10 then it is replaced with 'X'. Example: Data is 954123 Character position 0 1 2 3 4 5 Digit 9 5 4 1 2 3 Multiplier 1 3 1 3 1 3 Product 9 15 4 3 2 9 Sum of products = 9 + 15 + 4 + 3 + 2 + 9 = 42 Divide sum of products by 10: 42 / 10 = 4 (rounded down) The check digit = 4. This is inserted into character position 6. The data including the check digit is: 9541234 A 7‑character string is valid if the 7th character matches the check digit for that data. For example, the data 9541235 is invalid because the 7th character (5) does not match the check digit for 954123. (i) The subroutine StoreItems() takes ten 7‑character strings as input from the user and uses the check digit to validate each input. Each valid input has the check digit removed and is stored in the queue using Enqueue(). An appropriate message is output if the item is inserted. An appropriate message is output if the queue is already full. Invalid inputs are not stored in the queue. The subroutine counts and outputs the number of invalid items that were entered. StoreItems() can be a procedure or a function as appropriate. Write program code for StoreItems(). Save your program. Copy and paste the program code into part 3(d)(i) in the evidence document. [6] (ii) Write program code to amend the main program to: • call StoreItems() • call Dequeue() • output a suitable message if the queue was empty • output the returned value if the queue was not empty. Save your program. Copy and paste the program code into part 3(d)(ii) in the evidence document. [1] (iii) Test the program with the following inputs in the order given: 999999X 1251484 5500212 0033585 9845788 6666666 3258746 8111022 7568557 0012353 Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 3(d)(iii) in the evidence document. [2] BLANK PAGE BLANK PAGE Permission to reproduce items where third‑party owned material protected by copyright is included has been sought and cleared where possible. Every reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the publisher will be pleased to make amends at the earliest possible opportunity. To avoid the issue of disclosure of answer‑related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cambridgeinternational.org after the live examination series. Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge BLANK PAGE

Show mark scheme

3(a) [1 mark]

1 mark each
QueueData
as 1D (string) array initialised to 20 null values
and
QueueHead
initialised to
-1
,
QueueTail
initialised to
-1
class Queue{
public static String[] QueueData = new String[20];
public static Integer QueueHead;
public static Integer QueueTail;
public static void main(String args[]){
for(Integer x = 0; x < 20; x++){
QueueData[x] = "";
}
QueueHead = -1;
QueueTail = -1;
}
VB.NET
Dim QueueData(0 To 20) As String
Dim QueueHead As Integer = -1
Dim QueueTail As Integer = -1
Sub Main(args As String())
For x = 0 To 19
QueueData(x) = ""
Next
End Sub
Python
global QueueData
global QueueHead
global QueueTail
QueueData = []
for x in range(0, 20):
QueueData.append("")
QueueHead = -1
QueueTail = -1

3(b)

Python
def Enqueue(DataToInsert):
global QueueData
global QueueHead
global QueueTail
if QueueTail == 19:
return False
elif QueueHead == -1:
QueueHead = 0
QueueTail = QueueTail + 1
QueueData.append(DataToInsert)
return True

3(c)

Python
def Dequeue():
global QueueData
global QueueHead
global QueueTail
if QueueHead < 0 or QueueHead > 20 or QueueHead > QueueTail:
return False
else:
QueueHead = QueueHead + 1
return QueueData[QueueHead-1]

3(d)(i)

Python
def StoreItems():
global QueueData
global QueueHead
global QueueTail
Count = 0
for X in range(0, 10):
Data = input("Enter data")
Total= int(Data[0]) + int(Data[1]) * 3 + int(Data[2]) + int(Data[3]) * 3 +
int(Data[4]) + int(Data[5]) * 3
Total = int(Total / 10)
if((Total == 10 and Data[6] == "X") or (Total == int(Data[6]))):
Result = Enqueue(Data[0:6])
if(Result == True):
print("Inserted item")
else:
print("Queue full")
else:
Count = Count + 1
print("There were", Count,"Invalid items")

3(d)(ii)

Python
QueueData = []
for x in range(0, 20):
QueueData.append("")
QueueHead = -1
QueueTail = -1
StoreItems()
Value = Dequeue()
if Value == False:
print("No data items")
else:
print("Item code", Value)

3(d)(iii) [2 marks]

1 mark each
Data input of 10 values
and
output a message saying there are 4 invalid items
999999 output

May/Jun 2024 Paper 4 v2 2 marks

2 A binary tree stores data in ascending order. For example: 15 19 8 3 10 A computer program stores integers in a binary tree in ascending order. The program uses Object‑Oriented Programming (OOP). The binary tree is stored as a 1D array of nodes. Each node contains a left pointer, a data value and a right pointer. The class Node stores the data about a node. Node LeftPointer : INTEGER Data : INTEGER RightPointer : INTEGER stores the index of the node to the left in the binary tree stores the node’s data stores the index of the node to the right in the binary tree Constructor() GetLeft() GetRight() GetData() SetLeft() SetRight() SetData() initialises Data to its parameter value initialises LeftPointer and RightPointer to −1 returns the left pointer returns the right pointer returns the data value assigns the parameter to the left pointer assigns the parameter to the right pointer assigns the parameter to the data (a) (i) Write program code to declare the class Node and its constructor. Do not declare the other methods. Use the appropriate constructor for your programming language. If you are writing in Python, include attribute declarations using comments. Save your program as Question2_J24. Copy and paste the program code into part 2(a)(i) in the evidence document. [4] (ii) The get methods GetLeft(), GetRight()and GetData()each return the relevant attribute. Write program code for the three get methods. Save your program. Copy and paste the program code into part 2(a)(ii) in the evidence document. [3] (iii) The set methods SetLeft(), SetRight()and SetData()each take a parameter and then store this in the relevant attribute. Write program code for the three set methods. Save your program. Copy and paste the program code into part 2(a)(iii) in the evidence document. [3] (b) The class TreeClass stores the data about the binary tree. TreeClass Tree[0:19] : Node FirstNode : INTEGER NumberNodes : INTEGER an array of 20 elements of type Node stores the index of the first node in the tree stores the quantity of nodes in the tree Constructor() InsertNode() OutputTree() initialises FirstNode to −1 and NumberNodes to 0 initialises each element in Tree to a Node object with the data value of −1 takes a Node object as a parameter, inserts it in the array and updates the pointer for its parent node outputs the left pointer, data and right pointer of each node in Tree Nodes cannot be deleted from this tree. (i) Write program code to declare the class TreeClass and its constructor. Do not declare the other methods. Use the appropriate constructor for your programming language. If you are writing in Python, include attribute declarations using comments. Save your program. Copy and paste the program code into part 2(b)(i) in the evidence document. [4] (ii) The method InsertNode()takes a Node object, NewNode, as a parameter and inserts it into the array Tree. InsertNode()first checks if the tree is empty. If the tree is empty, InsertNode(): • stores NewNode in the array Tree at index NumberNodes • increments NumberNodes • stores 0 in FirstNode. If the tree is not empty, InsertNode(): • stores NewNode in the array Tree at index NumberNodes • accesses the data in the array Tree at index FirstNode and compares it to the data in NewNode • repeatedly follows the pointers until the correct position for NewNode is found • once the position is found, InsertNode()sets the left or right pointer of its parent node • increments NumberNodes. Write program code for InsertNode(). Save your program. Copy and paste the program code into part 2(b)(ii) in the evidence document. [6] (iii) The method OutputTree()outputs the left pointer, the data and the right pointer for each node that has been inserted into the tree. The outputs are in the order they are saved in the array. If there are no nodes in the array, the procedure outputs ‘No nodes’. Write program code for OutputTree(). Save your program. Copy and paste the program code into part 2(b)(iii) in the evidence document. [4] (c) (i) The main program declares an instance of TreeClass with the identifier TheTree. Write program code for the main program. Save your program. Copy and paste the program code into part 2(c)(i) in the evidence document. [1] (ii) The main program inserts the following integers into the binary tree in the order given: 10 11 5 1 20 7 15 The main program then calls the method OutputTree(). Write program code to amend the main program. Save your program. Copy and paste the program code into part 2(c)(ii) in the evidence document. [4] (iii) Test your program. Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 2(c)(iii) in the evidence document. [1]

Show mark scheme

2(a)(i)

Python
class Node():
def init (self, PData):
self. LeftPointer = -1 #int
self. Data = PData #int
self. RightPointer = -1 #int

2(a)(ii)

def GetRight(self):
return self. RightPointer
def GetData(self):
return self. Data

2(a)(iii)

self. RightPointer = NewRight
def SetData(self, NewData):
self. Data = NewData

2(b)(i)

For x = 0 To 19
Tree(x) = New Node(-1)
Next
End Sub
End Class
Python
class TreeClass():
def init (self):
self. Tree = [] #type node 20 spaces
self. FirstNode = -1 #int
self. NumberNodes = 0 #int
for x in range(20):
self. Tree.append(Node(-1))

2(b)(ii)

NodeAccess = self. Tree[NodeAccess].GetLeft()
Direction = "left"
elif NewNode.GetData() > self. Tree[NodeAccess].GetData():
NodeAccess = self. Tree[NodeAccess].GetRight()
Direction = "right"
if(Direction == "left"):
self. Tree[Previous].SetLeft(self. NumberNodes)
else:
self. Tree[Previous].SetRight(self. NumberNodes)
self. NumberNodes = self. NumberNodes + 1

2(b)(iii)

Python
def OutputTree(self):
if self. NumberNodes == 0:
print("No nodes")
else:
for x in range(0, self. NumberNodes):
print(self. Tree[x].GetLeft(), " ", self. Tree[x].GetData(), " ",self.
Tree[x].GetRight())

2(c)(i) [1 mark]

1 mark for
Instance of
TreeClass
created with identifier
TheTree
public static void main(String args[]){
TreeClass TheTree = new TreeClass();
VB.NET
Sub Main(args As String())
Dim TheTree As TreeClass = New TreeClass()
End Sub
Python
TheTree = TreeClass()

2(c)(ii)

Python
TheTree = TreeClass()
TheTree.InsertNode(Node(10))
TheTree.InsertNode(Node(11))
TheTree.InsertNode(Node(5))
TheTree.InsertNode(Node(1))
TheTree.InsertNode(Node(20))
TheTree.InsertNode(Node(7))
TheTree.InsertNode(Node(15))
TheTree.OutputTree()

2(c)(iii) [1 mark]

1 mark for correct output e.g.

May/Jun 2024 Paper 4 v2 9 marks

3 A program sorts an array of integers and searches the array for a particular value. (a) The array of integers, NumberArray, stores the following data in the order given: 100 85 644 22 15 8 1 The array is declared and initialised local to the main program. Write program code to declare and initialise the array. Save your program as Question3_J24. Copy and paste the program code into part 3(a) in the evidence document. [1] (b) (i) The following recursive pseudocode function sorts the array into ascending order using an insertion sort and returns the sorted array. DECLARE LastItem : INTEGER DECLARE CheckItem : INTEGER DECLARE LoopAgain : BOOLEAN FUNCTION RecursiveInsertion(IntegerArray : ARRAY[] OF INTEGER, NumberElements : INTEGER) RETURNS ARRAY[] OF INTEGER IF NumberElements <= 1 THEN RETURN IntegerArray ELSE CALL RecursiveInsertion(IntegerArray, NumberElements - 1) LastItem IntegerArray[NumberElements - 1] CheckItem NumberElements - 2 ENDIF LoopAgain TRUE IF CheckItem < 0 THEN LoopAgain FALSE ELSE IF IntegerArray[CheckItem] < LastItem THEN LoopAgain FALSE ENDIF ENDIF WHILE LoopAgain IntegerArray[CheckItem + 1] IntegerArray[CheckItem] CheckItem CheckItem - 1 IF CheckItem < 0 THEN LoopAgain FALSE ELSE IF IntegerArray[CheckItem] < LastItem THEN LoopAgain FALSE ENDIF ENDIF ENDWHILE IntegerArray[CheckItem + 1] LastItem RETURN IntegerArray ENDFUNCTION Write the program code for the pseudocode function RecursiveInsertion(). Save your program. Copy and paste the program code into part 3(b)(i) in the evidence document. [4] (ii) Amend the main program to: • call RecursiveInsertion()with the initialised array NumberArray and the number of elements as parameters • output the word ‘Recursive’ • output the content of the returned array. Save your program. Copy and paste the program code into part 3(b)(ii) in the evidence document. [2] (iii) Test your program. Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 3(b)(iii) in the evidence document. [1] (c) The function RecursiveInsertion()can be changed to use iteration instead of recursion. (i) Write program code for the function IterativeInsertion()to perform the same processes as RecursiveInsertion()but using iteration instead of recursion. Save your program. Copy and paste the program code into part 3(c)(i) in the evidence document. [4] (ii) Write program code to amend the main program to also: • call IterativeInsertion()with the original initialised array NumberArray • output the word ‘iterative’ • output the content of the returned array. Save your program. Copy and paste the program code into part 3(c)(ii) in the evidence document. [1] (iii) Test your program. Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 3(c)(iii) in the evidence document. [1] (d) The recursive function BinarySearch()takes the parameters: • IntegerArray – an array of integers • First – the index of the first array element • Last – the index of the last array element • ToFind – an integer to search for in the array. The function uses recursion to perform a binary search for ToFind in IntegerArray. The function returns the index where ToFind is stored or returns −1 if ToFind is not in the array. (i) Write program code for the recursive function BinarySearch(). Save your program. Copy and paste the program code into part 3(d)(i) in the evidence document. [6] (ii) Write program code to amend the main program to: • call BinarySearch()with the sorted array and the integer 644 as the search value • output ‘Not found’ if 644 is not found in the array • output the index if 644 is found in the array. Save your program. Copy and paste the program code into part 3(d)(ii) in the evidence document. [2] (iii) Test your program. Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 3(d)(iii) in the evidence document. [1] BLANK PAGE BLANK PAGE Permission to reproduce items where third‑party owned material protected by copyright is included has been sought and cleared where possible. Every reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the publisher will be pleased to make amends at the earliest possible opportunity. To avoid the issue of disclosure of answer‑related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cambridgeinternational.org after the live examination series. Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge BLANK PAGE

Show mark scheme

3(a) [1 mark]

1 mark each
NumberArray
declared (in main) with the 7 correct values in order (integer) 100 85 644 22 15 8 1
public static void main(String args[]){
Integer[] NumberArray = new Integer[7];
NumberArray[0] = 100;
NumberArray[1] = 85;
NumberArray[2] = 644;
NumberArray[3] = 22;
NumberArray[4] = 15;
NumberArray[5] = 8;
NumberArray[6] = 1;
VB.NET
Sub Main(args As String())
Dim NumberArray(7) As Integer
NumberArray(0) = 100
NumberArray(1) = 85
NumberArray(2) = 644
NumberArray(3) = 22
NumberArray(4) = 15
NumberArray(5) = 8
NumberArray(6) = 1
EndSub
Python
NumberArray = [100, 85, 644, 22, 15, 8, 1]

3(b)(i)

LoopAgain = False
End If
End While
IntegerArray(CheckItem + 1) = LastItem
Return IntegerArray
End Function
Python
def RecursiveInsertion(IntegerArray, NumberElements):
if NumberElements <= 1:
return IntegerArray
RecursiveInsertion(IntegerArray,NumberElements - 1)
LastItem = IntegerArray[NumberElements - 1]
CheckItem = NumberElements - 2
LoopAgain = True
if CheckItem < 0:
LoopAgain = False
elif IntegerArray[CheckItem] <= LastItem:
LoopAgain = False
while (LoopAgain):
IntegerArray[CheckItem + 1] = IntegerArray[CheckItem]
CheckItem = CheckItem - 1
if CheckItem < 0:
LoopAgain = False
elif IntegerArray[CheckItem] <= LastItem:
LoopAgain = False
IntegerArray[CheckItem + 1] = LastItem return IntegerArray

3(b)(ii) [2 marks]

1 mark each
Calling
RecursiveInsertion()
with array and number of elements (7 or length)
Outputting ‘recursive’ and then each element in
returned
array
Integer[] SortedArray = new Integer[7];
SortedArray = RecursiveInsertion(NumberArray, 7);
System.out.println("Recursive");
for(Integer x = 0; x < 7; x++){
System.out.println(SortedArray[x]);
VB.NET
SortedArray = RecursiveInsertion(NumberArray, 7)
Console.WriteLine("Recursive")
For x = 0 To 6
Console.WriteLine(SortedArray(x))
Next x
Python
SortedArray = RecursiveInsertion(NumberArray, len(NumberArray))
print("Recursive", SortedArray)

3(b)(iii) [1 mark]

1 mark for screenshot with:
Recursive

3(c)(i)

Python
def IterativeInsertion(IntegerArray, NumberElements):
while NumberElements > 0:
LastItem = IntegerArray[NumberElements - 1]
CheckItem = NumberElements - 2
LoopAgain = True
if CheckItem < 0:
LoopAgain = False
elif IntegerArray[CheckItem] <= LastItem:
LoopAgain = False
while(LoopAgain):
IntegerArray[CheckItem + 1] = IntegerArray[CheckItem]
CheckItem = CheckItem - 1
if CheckItem < 0:
LoopAgain = False
elif IntegerArray[CheckItem] <= LastItem:
LoopAgain = False
IntegerArray[CheckItem + 1] = LastItem
NumberElements = NumberElements - 1
return IntegerArray

3(c)(ii) [1 mark]

1 mark each
Calling
IterativeInsertion()
with original unsorted array and outputting ‘iterative’ and the content of the
returned
array
Integer[] Sorted2Array = new Integer[7];
Sorted2Array = IterativeInsertion(NumberArray, 7);
System.out.println("iterative");
for(Integer x = 0; x < 7; x++){
System.out.println(Sorted2Array[x]);
VB.NET
Sorted2Array = IterativeInsertion(NumberArray, 7)
Console.WriteLine("iterative")
For x = 0 To 6
Console.WriteLine(Sorted2Array(x))
Next x
Python
Sorted2Array = IterativeInsertion(NumberArray, len(NumberArray))
print("iterative", Sorted2Array)

3(c)(iii) [1 mark]

1 mark for Recursive
1 8 15 22 85 100 644
Iterative
1 8 15 22 85 100 644

3(d)(i)

Return -1
Else
Middle = (Last + First) \ 2
If IntegerArray(Middle) = ToFind Then
Return Middle
ElseIf IntegerArray(Middle) > ToFind Then
Return BinarySearch(IntegerArray, First, Middle - 1, ToFind)
Else
Return BinarySearch(IntegerArray, Middle + 1, Last, ToFind)
End If
End If
End Function
Python
def BinarySearch(IntegerArray, First, Last, ToFind):
if First > Last:
return -1
else:
Middle = int((Last + First) / 2)
if IntegerArray[Middle] == ToFind:
return Middle
elif IntegerArray[Middle] > ToFind:
return BinarySearch(IntegerArray, First, Middle - 1, ToFind)
else:
return BinarySearch(IntegerArray, Middle + 1, Last, ToFind)

3(d)(ii) [2 marks]

1 mark each
Calling
BinarySearch
function with sorted array, 0, 6/len(array)–1, 644 as parameters
Checking return value and outputting ‘Not found’ if –1 and index otherwise
Position = BinarySearch(Sorted2Array, 0, 6, 644);
if(Position == -1){
System.out.println("Not found");
}else{
System.out.println(Position);
VB.NET
Position = BinarySearch(Sorted2Array, 0, 6, 644)
If Position = -1 Then
Console.WriteLine("Not found")
Console.WriteLine(Position)
End If
Python
Position = BinarySearch(Sorted2Array, 0, len(NumberArray)-1, 644)
if Position == -1:
print("Not found")
else:
print(Position)

3(d)(iii) [1 mark]

1 mark for screenshot showing found in index 6 e.g.

May/Jun 2024 Paper 4 v3 12 marks