ZNOTES.

ORG

UPDATED TO 2023-2025 SYLLABUS

CAIE A2 LEVEL
COMPUTER SCIENCE
SUMMARIZED NOTES ON THE THEORY SYLLABUS
Prepared for sasha for personal use only.
CAIE A2 LEVEL COMPUTER SCIENCE

The middle item/index of the list is found

1. Sorting and Searching Item at the middle of the list is compared to item user
inputs
Algorithms If the item in the middle of the list is the same as the
item that the user inputs, a message saying “item found”
Part of the Computational Thinking and Problem-Solving will be output.
Chapter If the item is greater than what the user inputted, all the
items at the index lower than the middle index are
discarded.
1.1. Linear Search If the item is lower than what the user inputted, all the
items at the index greater than the middle index are
How does it work?
discarded.
The user is asked to enter an item they want to find in an The above steps are repeated until the item searched for
array. is found
All elements of an array are searched one by one until If one item is left in the list and it is not the item
the item the user entered is found. searched for, a message saying “item not found” is
When an item is found, the algorithm outputs an outputted.
appropriate message saying that the item is found and
The binary search algorithm has a Big O notion of O(log n).
which index/location the item is at.
The log is of base 2.
If the particular item is not found, the algorithm outputs
an appropriate message saying that the item is not
Python Code
found.
def binary_search(arr, target):
The linear search algorithm has a Big O notion of O(n).

Python Code low, high = 0, len(arr) - 1

while low <= high:

mid = (low + high) // 2
mid_element = arr[mid]

if mid_element == target:

1.2. Binary Search return f"Item {target} found at index {mid}.

elif mid_element < target:
low = mid + 1
The necessary condition for a binary search is that the
else:
list/array being searched must be ordered/sorted.
high = mid - 1

How Does It Work?

return f"Item {target} not found in the array."

1.3. Bubble Sort

How Does It Work?

WWW.ZNOTES.ORG Copyright © 2025 ZNotes Education & Foundation. All Rights Reserved. This document is
authorised for personal use only by sasha at undefined on 20/01/25.
CAIE A2 LEVEL COMPUTER SCIENCE

Bubble sort compares adjacent elements in the list/array. def insertion_sort(arr):

They are swapped if the elements are in the wrong order for i in range(1, len(arr)):
(according to the desired sorting). key = arr[i]
The algorithm iterates through the array multiple times j = i - 1
in passes.
On each pass, the largest unsorted element "bubbles up" # Move elements of arr[0..i-1] that are grea
to its correct position at the end of the array. while j >= 0 and key < arr[j]:
The process is repeated until the entire array is sorted. arr[j + 1] = arr[j]
j -= 1
Python Code
arr[j + 1] = key
def bubble_sort(arr):
n = len(arr) In the worst case, it has a time complexity of O(n^2), where n
# Traverse through all array elements is the number of elements in the array.
for i in range(n): Insertion sort is efficient for small datasets or partially
# Last i elements are already sorted, so we don' sorted datasets.
for j in range(0, n-i-1):
# Swap if the element found is greater than
if arr[j] > arr[j+1]:
2. Abstract Data Types (ADTs)
arr[j], arr[j+1] = arr[j+1], arr[j]
Part of the Computational Thinking and Problem-Solving
In the worst case, it has a time complexity of O(n^2), where n Chapter
is the number of elements in the array.
2.1. Stacks
1.4. Insertion Sort
Stack – an ADT where items can be popped or pushed
How Does It Work? from the top of the stack only
LIFO – Last In First Out data structure
The algorithm starts with the assumption that the first
element in the array is already sorted. Popping (pseudocode)
It then compares the next element with the sorted
portion of the array.
If the next element is smaller, it shifts the larger PROCEDURE PopFromStack
elements to the right until it finds the correct position for
the next element and inserts it there. IF TopOfStack = -1
The sorted portion of the array grows with each iteration
until the entire array is sorted. THEN
The process is repeated until all elements are in their
correct positions. OUTPUT “Stack is already empty”

Python Code ELSE

OUTPUT MyStack[ TopOfStack ] “is popped”

TopOfStack ← TopOfStack – 1

ENDIF

ENDPROCEDURE

WWW.ZNOTES.ORG Copyright © 2025 ZNotes Education & Foundation. All Rights Reserved. This document is
authorised for personal use only by sasha at undefined on 20/01/25.
CAIE A2 LEVEL COMPUTER SCIENCE

Pushing (pseudocode) 2.3. Linked Lists

PROCEDURE PushToStack

IF TopOfStack = MaxStackSize

THEN

OUTPUT “Stack is full”

ELSE

TopOfStack = TopOfStack + 1

MyStack[TopOfStack] = NewItem

ENDIF

ENDPROCEDURE

Use of Stacks:
Interrupt Handling
The contents of the register and the PC are saved and
put on the stack when the interrupt is detected
The return addresses are saved onto the stack as well
Retrieve the return addresses and restore the
register contents from the stack once the interrupt
has been serviced
Evaluating mathematical expressions held in Reverse
Polish Notation
Procedure Calling
Every time a new call is made, the return address
must be stored
Return addresses are recalled in the order ‘the last
one stored will be the first to be recalled.’
If there are too many nested calls, then stack
overflow

2.2. Queues

WWW.ZNOTES.ORG Copyright © 2025 ZNotes Education & Foundation. All Rights Reserved. This document is
authorised for personal use only by sasha at undefined on 20/01/25.
CAIE A2 LEVEL COMPUTER SCIENCE

Binary Tree
START at Root Node

REPEAT

IF WantedItem = ThisItem

THEN Found = TRUE

ELSE

IF WantedItem > ThisItem

2.4. Binary Tree
THEN Follow Right Pointer

ELSE Follow Left Pointer

UNTIL Found or Null Pointer Encountered

3. Recursion
Part of the Computational Thinking and Problem-Solving
Chapter

3.1. Essential Features of a Recursion

Must have a base case/stopping condition
Must have a general case which calls itself (recursively) //
Defined in terms of itself
The general case should be changing its state and move
toward the base case
Unwinding occurs once the base case is reached.

WWW.ZNOTES.ORG Copyright © 2025 ZNotes Education & Foundation. All Rights Reserved. This document is
authorised for personal use only by sasha at undefined on 20/01/25.
CAIE A2 LEVEL COMPUTER SCIENCE

Objects: Instances of classes representing real-world

3.2. Advantages and Disadvantages of a entities.
Recursion Properties/Attributes: The data items/attributes and
the data types // characteristics defined in a class.
Advantages Disadvantages Methods: the procedures/ functions / programmed
Less efficient in terms of instructions in a class that act on the
Can produce simpler, more properties/attributes.
computer time and storage
natural solutions to a problem
space Classes: Blueprint for creating objects with shared
A lot more storage space is attributes and methods.
used to store return addresses Inheritance: It is a mechanism for creating a new class
and states. based on an existing one, inheriting its attributes and
This could lead to infinite methods. Through inheritance, attributes contained in
recursion. one class (parent class) are made available to / reused by
another class (child class).
3.3. How A Compiler Translates Polymorphism: Ability to use different classes through a
common interface. It allows the same method to take on
Recursive Programming Code different behaviours depending on which class is
instantiated. These methods can be redefined for
Before the procedure call is executed, the current state of
derived classes.
the registers/local variables is saved onto a stack.
Containment (Aggregation): Combining multiple
When returning from a procedure call, the registers/local objects to create a more complex object.
variables are re-instated on the stack Encapsulation: Hiding the internal details of a class from
When the stopping condition/base case is met, the the outside.
algorithm unwinds the last set of values that are taken Getters and Setters: Methods for accessing and
off the stack (in reverse order) modifying object attributes. Get methods/Getters are
used to access attributes, while set methods/setters are
used to modify object attributes.
4. Object-Oriented Instances: Individual objects created from a class.

Programming 4.2. Constructor

Part of the Further Programming Chapter Constructors are functions that are used for initializing the
attributes/Properties of a class.
4.1. Key Terms & Definitions A constructor in Object-Oriented Programming (OOP) is a
special method within a class that is automatically called
when an object of that class is created.
Its primary purpose is to initialize the object's attributes
or perform setup actions.
In Python, the constructor is typically named init and
takes the self parameter, which refers to the created
object.
Inside the constructor, you initialize the object's
attributes.

For example:

WWW.ZNOTES.ORG Copyright © 2025 ZNotes Education & Foundation. All Rights Reserved. This document is
authorised for personal use only by sasha at undefined on 20/01/25.
CAIE A2 LEVEL COMPUTER SCIENCE
• Inheritance is a fundamental concept in OOP that allows
you to create a new class (a derived or child class) based on
an existing class (a base or parent class).
• The child class inherits the attributes and methods of the
parent class and can also add new attributes and methods
or override the ones inherited.
When you create an instance of the class, the constructor
In the context of the Person class, Inheritance would involve
is invoked automatically to set the object's initial state.
creating a child class, such as a Student or Employee, that
This ensures that objects are created in a valid and
inherits attributes and methods from the Person class. For
consistent state.
example, a Student class could inherit the name and age
attributes and the get_name method from the Person class.
4.3. Defining Classes and Methods
Polymorphism
• To define a class in Python, use the class keyword followed
by the class name. • Polymorphism is the ability of different classes to be
• Inside the class, you can define attributes (variables) and treated as instances of a common base class. It allows
methods (functions) that belong to the class. objects of different classes to be used interchangeably if
Here's a simple example of defining a class called Person they implement the same methods or interface.
with attributes and methods as shown below: • Polymorphism promotes flexibility and extensibility in your
code.
In the context of the Person class, Polymorphism could be
applied when you have different types of persons, such as
students, employees, and teachers, each having a get_name
method. You can call get_name on instances of these
different classes without knowing their specific type, as long
as they all have a get_name method.

Encapsulation
• Encapsulation is the practice of hiding the internal details
4.4. Get and Set Methods of a class and providing a controlled interface to access and
modify the class's attributes.
These methods are used to access/change attributes set to • This helps maintain the integrity and consistency of the
be private in a class. These methods are decelerated inside object's state by controlling how data is accessed and
the class. modified.
In the context of the Person class, Encapsulation is applied
by making the name attribute private (by convention, using a
leading underscore). This indicates that __name it should not
be accessed directly from outside the class. Instead, you
provide a controlled interface through the get_name and
set_name methods, ensuring that name changes are
validated and controlled.
Below is a brief code example illustrating how inheritance,
polymorphism, and encapsulation could be applied to the
Person class:

4.5. Inheritance

WWW.ZNOTES.ORG Copyright © 2025 ZNotes Education & Foundation. All Rights Reserved. This document is
authorised for personal use only by sasha at undefined on 20/01/25.
CAIE A2 LEVEL COMPUTER SCIENCE

• In the example above, the Student class inherits from the

Person class, demonstrating the concept of inheritance.
• Both classes can be treated interchangeably when calling
the get_name method, showing polymorphism.
• Encapsulation is maintained by controlling access to the
name attribute through getter and setter methods.

WWW.ZNOTES.ORG Copyright © 2025 ZNotes Education & Foundation. All Rights Reserved. This document is
authorised for personal use only by sasha at undefined on 20/01/25.
CAIE A2 Level
Computer Science

© ZNotes Education Ltd. & ZNotes Foundation 2024. All rights reserved.
This version was created by sasha on Mon Jan 20 2025 for strictly personal use only.
These notes have been created by Ashmit Bhola for the 2024-2025 syllabus.
The document contains images and excerpts of text from educational resources available on the internet and printed books.
If you are the owner of such media, test or visual, utilized in this document and do not accept its usage then we urge you to contact us
and we would immediately replace said media. No part of this document may be copied or re-uploaded to another website.
Under no conditions may this document be distributed under the name of false author(s) or sold for financial gain.
"ZNotes" and the ZNotes logo are trademarks of ZNotes Education Limited (registration UK00003478331).