ZNOTES.
ORG
UPDATED TO 2024-2025 SYLLABUS
CAIE A2 LEVEL
COMPUTER
SCIENCE
SUMMARIZED NOTES ON THE PRACTICAL SYLLABUS
Prepared for SDKLyrics JR for personal use only.
CAIE A2 LEVEL COMPUTER SCIENCE
Python Code
1. Sorting and Searching def binary_search(arr, target):
low, high = 0, len(arr) - 1
Algorithms while low <= high: mid = (low + high) // 2 mid_element =
arr[mid]
Part of the Computational Thinking and Problem-Solving
Chapter if mid_element == target:
return f"Item {target} found at index {mid}."
elif mid_element < target:
1.1. Linear Search low = mid + 1
else:
How does it work?
high = mid - 1
The user is asked to enter an item they want to find in an
return f"Item {target} not found in the array."
array.
All elements of an array are searched one by one until the
item the user entered is found. ## 1.3. Bubble Sort
When an item is found, the algorithm outputs an
appropriate message saying that the item is found and ### How Does It Work?
which index/location the item is at.
If the particular item is not found, the algorithm outputs * Bubble sort compares adjacent elements in the list/array
an appropriate message saying that the item is not found. * They are swapped if the elements are in the wrong order
* The algorithm iterates through the array multiple times i
The linear search algorithm has a Big O notion of O(n).
* On each pass, the largest unsorted element "bubbles up"
* The process is repeated until the entire array is sorted.
Python Code
### Python Code
def bubble_sort(arr): n = len(arr)
1.2. Binary Search Traverse through all array
The necessary condition for a binary search is that the elements
list/array being searched must be ordered/sorted.
for i in range(n): # Last i elements are already sorted, so we
How Does It Work? don't need to check them for j in range(0, n-i-1): # Swap if the
element found is greater than the next element if arr[j] >
The middle item/index of the list is found arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]
Item at the middle of the list is compared to item user
inputs
If the item in the middle of the list is the same as the item In the worst case, it has a time complexity of O(n^2), whe
that the user inputs, a message saying “item found” will be
output. ## 1.4. Insertion Sort
If the item is greater than what the user inputted, all the
items at the index lower than the middle index are ### How Does It Work?
discarded.
If the item is lower than what the user inputted, all the * The algorithm starts with the assumption that the first el
items at the index greater than the middle index are * It then compares the next element with the sorted portio
discarded. * If the next element is smaller, it shifts the larger element
The above steps are repeated until the item searched for * The sorted portion of the array grows with each iteration
is found * The process is repeated until all elements are in their cor
If one item is left in the list and it is not the item searched
for, a message saying “item not found” is outputted. ### Python Code
The binary search algorithm has a Big O notion of O(log n).
The log is of base 2.
WWW.ZNOTES.ORG Copyright © 2024 ZNotes Education & Foundation. All Rights Reserved. This document is authorised
for personal use only by SDKLyrics JR at DPS International, Gurgaon on 25/08/24.
CAIE A2 LEVEL COMPUTER SCIENCE
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j
* **Procedure Calling**
=i-1 * Every time a new call is made, the return address must
* Return addresses are recalled in the order ‘the last one
# Move elements of arr[0..i-1] that are greater than key to one
* Ifposition ahead
there are of their
too many current
nested position
calls, then stack overflow
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j] <!-- end list -->
j -= 1
## 2.2. Queues
arr[j + 1] = key
* **Queue**: an ADT where new elements are added at the
* **FIFO**: First In, First Out Data structure
In the worst case, it has a time complexity of O(n^2), where n is the number of elements in the array.
* **Creating a Circular Queue (pseudocode):**
Insertion sort is efficient for small datasets or partially sorted datasets.
```
PROCEDURE Initialise
# 2. Abstract Data Types (ADTs)
Front = 1
**Part of the Computational Thinking and Problem-Solving Chapter**
Rear = 6
## 2.1. Stacks
NumberInQueue := 0
* Stack – an ADT where items can be popped or pushed from the top of the stack only
* LIFO – Last In First Out data structure
END PROCEDURE
```
### **Popping (pseudocode)**
* **To add an Element to the Queue (pseudocode):**
PROCEDURE PopFromStack ```
IF TopOfStack = -1 PROCEDURE EnQueue
THEN
OUTPUT “Stack is already empty” IF NumberInQueue == 6
ELSE
OUTPUT MyStack[ TopOfStack ] “is popped” THEN Write (“Queue overflow”)
TopOfStack ← TopOfStack – 1
ENDIF ELSE
ENDPROCEDURE
IF Rear == 6
### **Pushing (pseudocode)** THEN Rear = 1
ELSE Rear = Rear + 1
PROCEDURE PushToStack
IF TopOfStack = MaxStackSize
ENDIF
THEN
OUTPUT “Stack is full”
Q[Rear] = NewItem
ELSE
TopOfStack = TopOfStack + 1
NumberInQueue =NumberInQueue +1
MyStack[TopOfStack] = NewItem
ENDIF
ENDIF
ENDPROCEDURE
ENDPROCEDURE
**<span class="underline">Use of Stacks:</span>**
```
* **Interrupt Handling** * The front of the queue is accessed through the pointer Fr
* To add an element
* The contents of the register and the PC are saved and put on the stack when thetointerrupt
the queue, the pointers have to be
is detected
* The return addresses are saved onto the stack as well * In some implementations, two pointers are kept: 1 to the
* Retrieve the return addresses and restore the register contents from the stack once the interrupt has been serviced:
* To Remove an Item from the Queue **(pseudocode)**
* **Evaluating mathematical expressions held in Reverse Polish Notation**
WWW.ZNOTES.ORG Copyright © 2024 ZNotes Education & Foundation. All Rights Reserved. This document is authorised
for personal use only by SDKLyrics JR at DPS International, Gurgaon on 25/08/24.
CAIE A2 LEVEL COMPUTER SCIENCE
PROCEDURE DeQueue 2. CurrentPointer points to the next node’s address
IF NumberInQueue == 0 3. If data in the node at CurrentPointer matches SearchIt
THEN Write (“Queue empty”) * Set the pointer of the node at PreviousPointer to the
ELSE * Set the pointer of the node at CurrentPointer to FreeP
NewItem = Q[Front] * Set FreePointer to CurrentPointer
NumberInQueue = NumberInQueue – 1 * Boolean value becomes true
IF Front ==6 * **If the Boolean value is false**
THEN Front = 1
ELSE
Front = Front + 1 1. Inform the user that the item to be deleted has not been
ENDIF
ENDIF 
IF Tree is empty THEN create new tree with Item as the root.
* Inserting into a Linked List
ELSE IF Item < Root
THEN insert(Left sub-tree of Tree, Item)
ELSE insert(Right sub-tree of Tree, Item)
ENDIF
ENDIF
* Searching a Linked List
ENDPROCEDURE
\ * Another common use of a binary tree is to hold an algebr
* Deleting an Item from a Linked List It could be stored as:
* Use a Boolean value to know when an item has been found and deleted (initially false)
* Use a pointer (CurrentPointer) to go through each node’s address
\
* If the new item is found in the header: 
* When you create an instance of the class, the constructo
# 3. Recursion ## 4.3. Defining Classes and Methods
**Part of the Computational Thinking and Problem-Solving Chapter**
• To define a class in Python, use the class keyword followe
## 3.1. Essential Features of a Recursion • Inside the class, you can define attributes (variables) and
* Must have a base case/stopping condition Here's a simple example of defining a class called Person w
* 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  based on an existing class (a base or parent
Before the procedure call is executed, the current state of the •registers/local
The child class
variables
inherits is
the
saved
attributes
onto aand
stack.
methods of the
attributes and methods or override the ones inherited.
* When returning from a procedure call, the registers/local variables are re-instated on the stack
* When the stopping condition/base case is met, the algorithmInunwinds
the context
the last
of the
setPerson
of values
class,
that
Inheritance
are taken off
would
the involv
stack
# 4. Object-Oriented Programming ### **Polymorphism**
**Part of the Further Programming Chapter** • Polymorphism is the ability of different classes to be trea
## 4.1. Key Terms & Definitions • Polymorphism promotes flexibility and extensibility in yo
* **Objects**: Instances of classes representing real-world entities.
In the context of the `Person` class, Polymorphism could b
* **Properties/Attributes**: The data items/attributes and the data types // characteristics defined in a class.
* **Methods**: the procedures/ functions / programmed instructions ### **Encapsulation**
in a class that act on the properties/attributes.
* **Classes**: Blueprint for creating objects with shared attributes and methods.
* **Inheritance**: It is a mechanism for creating a new class based• Encapsulation
on an existing
is the
one,
practice
inheriting
of hiding
its attributes
the internal
and detail
meth
* **Polymorphism**: Ability to use different classes through a common interface. It allows the same method to take on d
* **Containment (Aggregation)**: Combining multiple objects • toThis
create
helps
a more
maintain
complex
the integrity
object. and consistency of the o
* **Encapsulation**: Hiding the internal details of a class from the outside.
* **Getters and Setters**: Methods for accessing and modifying In object
the context
attributes.
of theGet
`Person`
methods/Getters
class, Encapsulation
are used to
is applie
acce
* **Instances**: Individual objects created from a class.
Below is a brief code example illustrating how inheritance,
## 4.2. Constructor
 is a special concept
method
of inheritance.
within a class that is automatically called whe
* 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. • Both classes can be treated interchangeably when calling
polymorphism.
**For example:**
 or sold for financial gain.
“ZNotes” and the ZNotes logo are trademarks of ZNotes Education Limited (registration UK00003478331).
