Chapter 19: Computational Thinking and Problem-Solving
9618 AS/A Level Computer Science - Algorithms
📚 Learning Objectives
Understand and write linear search algorithms
Understand and write binary search algorithms
Understand and write bubble sort algorithms
Understand and write insertion sort algorithms
Implement stacks using arrays and classes
Implement queues using arrays and classes
Understand linked list operations (create, traverse, add, remove)
Understand binary tree structures and traversals
Build one ADT on top of another ADT
Analyze algorithm suitability using Big-O notation
🌟 Prior Knowledge Required
Arrays and 1D/2D array manipulation
Loops (FOR, WHILE) and conditional statements (IF/ELSE)
Procedures and functions (subroutines)
Basic understanding of data types (INTEGER, STRING, BOOLEAN)
Understanding of record structures and classes
Recursion concepts (for tree traversals)
1. Linear Search
📖 What is Linear Search?
A linear search is a standard algorithm used to find elements in an unordered list. The list is searched sequentially and systematically from start to end, one element at a time, comparing each element to the value being searched for.
If the value is found → outputs the index position
If the value is not found → outputs a message stating it is not in the list
Works on unordered lists
1.1 How Linear Search Works
📝 Linear Search Algorithm Steps
Start at the beginning of the list (index 0)
Compare the current element with the target value
If they match, return the current index
If they don't match, move to the next element
Repeat until the item is found or end of list is reached
If not found, return -1 (or appropriate indicator)
1.2 Linear Search Pseudocode
Pseudocode - Linear Search
FUNCTION linearSearch(list : ARRAY OF STRING, item : STRING) RETURNS INTEGER
DECLARE index : INTEGER
DECLARE i : INTEGER
DECLARE found : BOOLEAN
index ← -1
i ← 0
found ← FALSE
WHILE i < LENGTH(list) AND found = FALSE
IF list[i] = item THEN
index ← i
found ← TRUE
ENDIF
i ← i + 1
ENDWHILE
RETURN index
ENDFUNCTION
1. Linear Search (Continued)
1.3 Linear Search in Python
Python Implementation
def linear_search(list, item):
index = -1
for i in range(len(list)):
if list[i] == item:
index = i
break # Stop the loop once found
return index
# Example usage
my_list = [5, 9, 4, 2, 6, 7, 1, 2, 4, 3]
result = linear_search(my_list, 7)
print(f"Item found at index: {result}")
1.4 Time & Space Complexity
Complexity Type
Big-O Notation
Explanation
Worst Case Time
O(n)
Item at end or not in list - checks all n items
Best Case Time
O(1)
Item found at first position
Average Case Time
O(n)
Item found halfway through list
Space Complexity
O(n)
Requires space for the list of n items
💡 Exam Tip
The time complexity O(n) means the execution time grows linearly with input size. If you double the list size, you (roughly) double the search time in worst case.
1.5 Trace Table Example
Given list [5, 4, 7, 1, 3, 8, 9, 2], searching for item 8:
item
index
i
list[i]
found
8
-1
0
5
False
1
4
False
2
7
False
3
1
False
4
3
False
5
5
8
True
2. Binary Search
📖 What is Binary Search?
A binary search is a more efficient search method than linear search. It compares the middle item to the target item and discards half of the list each time.
Requires the list to be sorted beforehand
Uses divide and conquer approach
If target < middle → search left half
If target > middle → search right half
Time complexity: O(log n)
⚠️ Important Requirement
The list MUST be sorted for binary search to work correctly. Binary search does not discard or delete items - it only adjusts the start, end, and mid pointers.
2.1 How Binary Search Works
📝 Binary Search Algorithm Steps
Set start = 0, end = length of list - 1
Calculate mid = (start + end) DIV 2
If list[mid] = target → return mid (found!)
If list[mid] < target → start = mid + 1 (search right half)
If list[mid] > target → end = mid - 1 (search left half)
Repeat while start <= end
If loop ends without finding → return -1
2. Binary Search (Continued)
2.2 Binary Search Pseudocode
Pseudocode - Binary Search
FUNCTION binarySearch(list : ARRAY OF INTEGER, item : INTEGER) RETURNS INTEGER
DECLARE found : BOOLEAN
DECLARE index : INTEGER
DECLARE start : INTEGER
DECLARE end : INTEGER
DECLARE mid : INTEGER
found ← FALSE
index ← -1
start ← 0
end ← LENGTH(list) - 1
WHILE start <= end AND found = FALSE
mid ← (start + end) DIV 2
IF list[mid] = item THEN
found ← TRUE
index ← mid
ELSE
IF list[mid] < item THEN
start ← mid + 1
ELSE
end ← mid - 1
ENDIF
ENDIF
ENDWHILE
RETURN index
ENDFUNCTION
2.3 Binary Search in Python
Python Implementation
def binary_search(list, item):
found = False
index = -1
start = 0
end = len(list) - 1
while start <= end and not found:
mid = (start + end) // 2
if list[mid] == item:
found = True
index = mid
elif list[mid] < item:
start = mid + 1
else:
end = mid - 1
return index
# Example usage (list must be sorted!)
sorted_list = [3, 5, 9, 10, 14, 16, 17, 21, 24, 26, 28, 30, 42, 44, 50, 51]
result = binary_search(sorted_list, 21)
print(f"Item found at index: {result}") # Output: 7
2.4 Time & Space Complexity
Complexity Type
Big-O Notation
Explanation
Worst Case Time
O(log n)
Halves search space each iteration
Best Case Time
O(1)
Item found at middle on first check
Average Case Time
O(log n)
Found somewhere in middle of search
Space Complexity
O(n)
Requires space for the sorted list
🧠 Memory Trick: Why O(log n)?
After each iteration, the search space is halved:
n → n/2 → n/4 → n/8 → ... → 1
Number of steps = log₂(n). For a list of 1,000,000 items: binary search takes at most 20 comparisons!
3. Bubble Sort
📖 What is Bubble Sort?
Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. The largest values "bubble" to the top (end) of the list.
Compares pairs of adjacent elements
Swaps them if they are in wrong order
After each pass, the largest unsorted element is in position
Continues until no swaps are needed
Time complexity: O(n²)
💡 Why "Bubble" Sort?
The highest value eventually "bubbles" its way to the top like bubbles in a fizzy drink!
3.1 How Bubble Sort Works
📝 Bubble Sort Algorithm Steps
Start at the beginning of the list
Compare first two elements
If first > second, swap them
Move to next pair and repeat
After reaching end, largest element is in final position
Start again from beginning (excluding sorted elements)
If a pass completes with no swaps → list is sorted!
3. Bubble Sort (Continued)
3.2 Bubble Sort Pseudocode
Pseudocode - Bubble Sort
DECLARE list : ARRAY[0:9] OF INTEGER
DECLARE last, i, j, temp : INTEGER
DECLARE swap : BOOLEAN
list ← [5, 9, 4, 2, 6, 7, 1, 2, 4, 3]
last ← LENGTH(list)
i ← 0
swap ← TRUE
WHILE i < (last - 1) AND swap = TRUE
swap ← FALSE
FOR j ← 0 TO last - i - 2
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
swap ← TRUE
ENDIF
NEXT j
i ← i + 1
ENDWHILE
OUTPUT list
3.3 Bubble Sort in Python
Python Implementation
def bubble_sort(list):
n = len(list)
for i in range(n - 1):
swapped = False
for j in range(0, n - i - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
swapped = True
if not swapped:
break # Early termination if no swaps
return list
# Example usage
my_list = [5, 9, 4, 2, 6, 7, 1, 2, 4, 3]
sorted_list = bubble_sort(my_list.copy())
print(f"Sorted list: {sorted_list}")
3.4 Time & Space Complexity
Complexity Type
Big-O Notation
Explanation
Worst Case Time
O(n²)
Reverse sorted list - many swaps needed
Best Case Time
O(n)
Already sorted - one pass with no swaps
Average Case Time
O(n²)
Random order list
Space Complexity
O(1)
In-place sorting - only needs temp variable
❌ Common Mistake
Students often forget the swap flag. Without it, the algorithm will always run (n-1) passes even if the list is already sorted. The swap flag allows early termination!
4. Insertion Sort
📖 What is Insertion Sort?
Insertion sort sorts one item at a time by placing each item in its correct position within the sorted portion. It works like sorting cards in your hand - you pick up each card and insert it in the right place.
First element is considered already sorted
Each subsequent element is inserted into correct position
Elements to the left are shifted right to make room
Efficient for small or partially sorted lists
Time complexity: O(n²) worst case
4.1 How Insertion Sort Works
📝 Insertion Sort Algorithm Steps
Start from the second element (index 1)
Store current element as "item"
Compare item with elements to its left
Shift larger elements one position right
Insert item in its correct position
Repeat for all remaining elements
4.2 Insertion Sort Pseudocode
Pseudocode - Insertion Sort
PROCEDURE insertionSort(list : ARRAY OF INTEGER)
DECLARE n, i, position : INTEGER
DECLARE item : INTEGER
n ← LENGTH(list)
FOR i ← 1 TO n - 1
item ← list[i]
position ← i
WHILE position > 0 AND list[position - 1] > item
list[position] ← list[position - 1]
position ← position - 1
ENDWHILE
list[position] ← item
NEXT i
ENDPROCEDURE
4. Insertion Sort (Continued)
4.3 Insertion Sort in Python
Python Implementation
def insertion_sort(data):
for i in range(1, len(data)):
item = data[i]
position = i
while position > 0 and data[position - 1] > item:
data[position] = data[position - 1]
position -= 1
data[position] = item
return data
# Example usage
my_list = [5, 9, 4, 2, 7, 1, 2, 4, 3]
sorted_list = insertion_sort(my_list.copy())
print(f"Sorted list: {sorted_list}")
4.4 Sorting Algorithm Comparison
Algorithm
Worst Case
Best Case
Space
When to Use
Bubble Sort
O(n²)
O(n)
O(1)
Small lists, nearly sorted data
Insertion Sort
O(n²)
O(n)
O(1)
Small lists, incremental sorting
💡 When to Choose Which Sort?
Bubble sort: When list is nearly sorted and you want early termination
Insertion sort: When adding items one at a time (incremental sorting)
Both have O(n²) worst case - avoid for large datasets!
4.5 Trace Table Example
Sorting list [5, 9, 4, 2, 7]:
i
item
position
Comparison
Result
1
9
1
9 > 5
Stay: [5, 9, 4, 2, 7]
2
4
2→1→0
4 < 9, 4 < 5
Insert at 0: [4, 5, 9, 2, 7]
3
2
3→2→1→0
2 < 9, 2 < 5, 2 < 4
Insert at 0: [2, 4, 5, 9, 7]
4
7
4→3
7 < 9, 7 > 5
Insert at 3: [2, 4, 5, 7, 9]
5. Stacks
📖 What is a Stack?
A stack is a linear Abstract Data Type (ADT) that follows the Last In, First Out (LIFO) principle. Think of a stack of plates - you can only add or remove from the top.
Items are added and removed from the same end (top)
Push: Add item to top of stack
Pop: Remove item from top of stack
Peek: View top item without removing
isEmpty: Check if stack is empty
isFull: Check if stack is full
5. Stacks (Continued)
5.1 Stack Operations Pseudocode
Pseudocode - Stack Operations
// Check if stack is empty
FUNCTION isEmpty(s : Stack) RETURNS BOOLEAN
RETURN s.top = -1
ENDFUNCTION
// Check if stack is full
FUNCTION isFull(s : Stack) RETURNS BOOLEAN
RETURN s.top = s.capacity - 1
ENDFUNCTION
// Push item onto stack
PROCEDURE push(s : REF Stack, value : INTEGER)
IF NOT isFull(s) THEN
s.top ← s.top + 1
s.items[s.top] ← value
ELSE
OUTPUT "Stack is full"
ENDIF
ENDPROCEDURE
// Pop item from stack
FUNCTION pop(s : REF Stack) RETURNS INTEGER
IF NOT isEmpty(s) THEN
DECLARE value : INTEGER
value ← s.items[s.top]
s.top ← s.top - 1
RETURN value
ELSE
RETURN -1
ENDIF
ENDFUNCTION
// Peek at top item
FUNCTION peek(s : Stack) RETURNS INTEGER
IF NOT isEmpty(s) THEN
RETURN s.items[s.top]
ELSE
RETURN -1
ENDIF
ENDFUNCTION
5.2 Stack Implementation in Python
Python Implementation
class Stack:
def __init__(self, capacity):
self.stack = []
self.capacity = capacity
def isEmpty(self):
return len(self.stack) == 0
def isFull(self):
return len(self.stack) == self.capacity
def push(self, value):
if not self.isFull():
self.stack.append(value)
else:
print("Stack is full")
def pop(self):
if not self.isEmpty():
return self.stack.pop()
else:
return None
def peek(self):
if not self.isEmpty():
return self.stack[-1]
else:
return None
def size(self):
return len(self.stack)
# Example usage
s = Stack(5)
s.push(10)
s.push(20)
s.push(30)
print(f"Top item: {s.peek()}") # Output: 30
print(f"Popped: {s.pop()}") # Output: 30
print(f"Current size: {s.size()}") # Output: 2
6. Queues
📖 What is a Queue?
A queue is a linear Abstract Data Type (ADT) that follows the First In, First Out (FIFO) principle. Like a real queue of people - first person to join is first to be served.
Items added at rear, removed from front
Enqueue: Add item to rear of queue
Dequeue: Remove item from front of queue
Peek/Front: View front item without removing
isEmpty: Check if queue is empty
isFull: Check if queue is full
💡 Stack vs Queue Difference
Stack: LIFO - Last In, First Out (like stacking plates)
Queue: FIFO - First In, First Out (like a line at a store)
6.1 Linear vs Circular Queue
Feature
Linear Queue
Circular Queue
Space Usage
Wastes space after dequeue
Reuses empty slots
Implementation
Simple, but items must shift
Uses MOD for wrap-around
Pointers
Front always at index 0
Both front and rear can move
Efficiency
O(n) for dequeue (shifting)
O(1) for all operations
6. Queues (Continued)
6.2 Queue Operations Pseudocode
Pseudocode - Circular Queue Operations
// Enqueue - Add to rear
PROCEDURE enqueue(q : REF Queue, item : STRING)
IF NOT isFull(q) THEN
q.rear ← (q.rear + 1) MOD q.capacity
q.items[q.rear] ← item
q.size ← q.size + 1
ELSE
OUTPUT "Queue is full"
ENDIF
ENDPROCEDURE
// Dequeue - Remove from front
FUNCTION dequeue(q : REF Queue) RETURNS STRING
IF NOT isEmpty(q) THEN
DECLARE value : STRING
value ← q.items[q.front]
q.front ← (q.front + 1) MOD q.capacity
q.size ← q.size - 1
RETURN value
ELSE
RETURN "Queue is empty"
ENDIF
ENDFUNCTION
// isEmpty and isFull
FUNCTION isEmpty(q : Queue) RETURNS BOOLEAN
RETURN q.size = 0
ENDFUNCTION
FUNCTION isFull(q : Queue) RETURNS BOOLEAN
RETURN q.size = q.capacity
ENDFUNCTION
6.3 Queue Implementation in Python
Python Implementation
from collections import deque
class Queue:
def __init__(self, capacity):
self.items = deque()
self.capacity = capacity
def isEmpty(self):
return len(self.items) == 0
def isFull(self):
return len(self.items) == self.capacity
def enqueue(self, item):
if not self.isFull():
self.items.append(item)
else:
print("Queue is full")
def dequeue(self):
if not self.isEmpty():
return self.items.popleft()
else:
return "Queue is empty"
def peek(self):
if not self.isEmpty():
return self.items[0]
else:
return None
def find(self, target):
return target in self.items
# Example usage
q = Queue(5)
q.enqueue("Alice")
q.enqueue("Bob")
q.enqueue("Charlie")
print(f"Front item: {q.peek()}") # Output: Alice
print(f"Dequeued: {q.dequeue()}") # Output: Alice
print(f"Is 'Bob' in queue? {q.find('Bob')}") # Output: True
7. Linked Lists
📖 What is a Linked List?
A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node. Unlike arrays, nodes are not stored in consecutive memory locations.
Each node contains: data + pointer to next node
Start pointer points to first node
Last node has a null pointer (end of list)
Dynamic size - can grow/shrink as needed
Efficient insertion/deletion at known positions
🌟 Key Terminology
Node: An element containing data and a pointer
Pointer: Variable storing address of another node
Null pointer: Points to nothing (end of list)
Start pointer: Points to first node
7. Linked Lists (Continued)
7.1 Linked List Operations
Pseudocode - Create Node Class
CLASS Node
DECLARE fruit : STRING
DECLARE next : Node
ENDCLASS
// Create nodes
DECLARE node1 : Node
DECLARE node2 : Node
DECLARE node3 : Node
SET node1 = NEW Node
SET node2 = NEW Node
SET node3 = NEW Node
// Assign values
SET node1.fruit = "apple"
SET node2.fruit = "banana"
SET node3.fruit = "orange"
// Connect nodes
SET node1.next = node2
SET node2.next = node3
SET node3.next = NULL
7.2 Traverse Linked List
Pseudocode - Traverse
// Start at the head of the list
DECLARE current : Node
SET current = node1
WHILE current != NULL
OUTPUT current.fruit
SET current = current.next
ENDWHILE
7.3 Python Implementation
Python Implementation
class Node:
def __init__(self, fruit):
self.fruit = fruit
self.next = None
# Create nodes
node1 = Node("apple")
node2 = Node("banana")
node3 = Node("orange")
# Connect nodes
node1.next = node2
node2.next = node3
# Traverse the linked list
current = node1
while current is not None:
print(current.fruit)
current = current.next
# Add new node to end
new_node = Node("grape")
current = node1
while current.next is not None:
current = current.next
current.next = new_node
7.4 Delete from Linked List
📝 Delete Algorithm Steps
Start traversal from head
Keep track of current and previous nodes
Find node with target value
If at head: update head to next node
Otherwise: set previous.next = current.next
Node is now removed from list
8. Binary Trees
📖 What is a Binary Tree?
A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. It's essentially a graph with a specific structure.
Root: The topmost node (no parent)
Leaf: Node with no children
Parent: Node with children
Child: Node connected below another node
Subtree: Section of tree including a node and its descendants
8.1 Tree Traversals
Traversal
Order
Use Case
Pre-order
Root → Left → Right
Copy tree, prefix expression
In-order
Left → Root → Right
Binary Search Tree (sorted output)
Post-order
Left → Right → Root
Delete tree, postfix expression
8. Binary Trees (Continued)
8.2 Tree Node Class Pseudocode
Pseudocode - Tree Node
CLASS TreeNode
DECLARE value : STRING
DECLARE children : ARRAY OF TreeNode
ENDCLASS
FUNCTION createTreeNode(val : STRING) RETURNS TreeNode
DECLARE node : TreeNode
SET node = NEW TreeNode
SET node.value = val
SET node.children = []
RETURN node
ENDFUNCTION
PROCEDURE addChild(parent : TreeNode, childValue : STRING)
DECLARE childNode : TreeNode
SET childNode = createTreeNode(childValue)
APPEND childNode TO parent.children
ENDPROCEDURE
8.3 Python Tree Implementation
Python Implementation
class TreeNode:
def __init__(self, value):
self.value = value
self.children = []
def createTreeNode(val):
return TreeNode(val)
def addChild(parent, childValue):
childNode = createTreeNode(childValue)
parent.children.append(childNode)
def traverseTree(node):
"""Pre-order traversal"""
if node is None:
return
print(node.value)
for child in node.children:
traverseTree(child)
# Example usage
root = createTreeNode("Root")
addChild(root, "Child 1")
addChild(root, "Child 2")
# Add grandchild to Child 1
child1 = root.children[0]
addChild(child1, "Grandchild 1.1")
# Traverse
traverseTree(root)
# Output: Root, Child 1, Grandchild 1.1, Child 2
8.4 Add and Remove Nodes
Python - Add and Remove
def addChild(parent, childValue):
childNode = TreeNode(childValue)
parent.children.append(childNode)
def removeChild(parent, targetValue):
for i in range(len(parent.children)):
if parent.children[i].value == targetValue:
del parent.children[i]
return
# Usage
addChild(root, "New Child")
removeChild(root, "Child 1")
9. Building ADT from ADT
📖 What Does It Mean?
You can build one Abstract Data Type on top of another. This demonstrates understanding of how data structures can be composed.
A stack can be implemented using a linked list
A queue can be implemented using two stacks
A dictionary can be implemented using a binary search tree
ADT Being Built
Uses This ADT
How It Works
Queue
Two Stacks
Enqueue in one, dequeue from other
Stack
Linked List
Push/pop from head of list
Binary Tree
Linked List/Array
Nodes link like a graph
Dictionary
Binary Search Tree
Keys stored in BST for lookup
10. Algorithm Analysis (Big-O)
📖 What is Big-O Notation?
Big-O Notation describes the time and space complexity of an algorithm - how it scales as input size increases. It's hardware-independent and measures steps/operations.
📝 Big-O Rules
Keep only the dominant term (largest growth rate)
Ignore constants - they become insignificant as input grows
O(2n) → O(n), O(n² + n) → O(n²)
Notation
Name
Example
Efficiency
O(1)
Constant
Access array element by index
⭐⭐⭐⭐⭐ Best
O(log n)
Logarithmic
Binary search
⭐⭐⭐⭐
O(n)
Linear
Linear search, single loop
⭐⭐⭐
O(n log n)
Linearithmic
Efficient sorts (merge, quick)
⭐⭐
O(n²)
Quadratic
Bubble sort, insertion sort
⭐ Slow
🧠 Remember the Order
O(1) < O(log n) < O(n) < O(n log n) < O(n²)
From fastest to slowest. For n=1,000,000: O(log n) ≈ 20 steps, O(n) = 1,000,000 steps, O(n²) = 1,000,000,000,000 steps!
11. Exam-Style Questions
1. Describe how a linear search algorithm works. Give the time complexity and explain when it should be used. [5 marks]
Answer:
Linear search starts at the beginning of a list and checks each element one at a time
Compares each element with the target value being searched for
If a match is found, returns the index position of the item
If no match is found after checking all elements, returns -1 (or indicator of not found)
Time complexity: O(n) worst case, O(1) best case
Should be used when list is unordered or when list is small
Works on any list - does not require sorted data
Additional points: Simple to implement, works on linked lists where random access isn't possible, can stop early if item is found.
2. A binary search is performed on a sorted array. Explain why the array must be sorted and describe the algorithm. Give the time complexity. [6 marks]
Answer:
The array must be sorted because binary search relies on comparing the middle element to determine which half to search
If unsorted, we cannot know if the target is in the left or right half
Algorithm: Set start=0, end=length-1
Calculate mid = (start + end) DIV 2
If array[mid] = target, return mid (found)
If array[mid] < target, set start = mid + 1 (search right half)
If array[mid] > target, set end = mid - 1 (search left half)
Repeat while start <= end
Time complexity: O(log n) - halves search space each iteration
Additional points: Uses divide and conquer approach, much faster than linear search for large sorted datasets.
3. Write pseudocode for a bubble sort algorithm that sorts an array into ascending order. Include a mechanism to terminate early if the list is already sorted. [8 marks]
Answer:
DECLARE list : ARRAY OF INTEGER
DECLARE n, i, j, temp : INTEGER
DECLARE swapped : BOOLEAN
n ← LENGTH(list)
i ← 0
REPEAT
swapped ← FALSE
FOR j ← 0 TO n - i - 2
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
swapped ← TRUE
ENDIF
NEXT j
i ← i + 1
UNTIL i >= n - 1 OR swapped = FALSE
Key points: (1) Outer loop uses swapped flag [1 mark], (2) Inner loop compares adjacent elements [1 mark], (3) Swap mechanism with temp variable [1 mark], (4) Early termination when no swaps [1 mark], (5) Correct loop boundaries [1 mark each for additional details].
4. Compare bubble sort and insertion sort. Give an example of when you would use each algorithm. [5 marks]
Answer:
Bubble sort: Compares adjacent pairs, swaps if out of order, largest "bubbles" to end
Insertion sort: Takes each element, inserts in correct position among sorted elements
Both have O(n²) worst case time complexity
Both have O(1) space complexity (in-place sorting)
Use bubble sort: When list is nearly sorted (can terminate early)
Use insertion sort: When adding items one at a time (incremental sorting)
Insertion sort is more efficient for small datasets
5. A stack is an abstract data type. Describe the operations that can be performed on a stack and explain the LIFO principle. [5 marks]
Answer:
LIFO = Last In, First Out - last item added is first to be removed
Push: Add an item to the top of the stack
Pop: Remove and return the item from the top of the stack
Peek: View the top item without removing it
isEmpty: Check if the stack contains any items
isFull: Check if the stack has reached its capacity
Like a stack of plates - can only add/remove from top
Real-world examples: Browser back button, undo function in editors, call stack in recursion.
11. Exam-Style Questions (Continued)
6. Explain the difference between a queue and a stack. Give a real-world example of where each would be used. [4 marks]
Answer:
Queue: FIFO (First In, First Out) - items added at rear, removed from front
Stack: LIFO (Last In, First Out) - items added and removed from same end (top)
Queue example: Print queue (first document sent is first printed), keyboard buffer, CPU scheduling
Stack example: Browser back button, undo function, recursion call stack
7. Write pseudocode for a circular queue's enqueue and dequeue operations. Explain why a circular queue is more efficient than a linear queue. [6 marks]
Answer:
// Enqueue
PROCEDURE enqueue(q : REF Queue, item : STRING)
IF NOT isFull(q) THEN
q.rear ← (q.rear + 1) MOD q.capacity
q.items[q.rear] ← item
q.size ← q.size + 1
ENDIF
ENDPROCEDURE
// Dequeue
FUNCTION dequeue(q : REF Queue) RETURNS STRING
IF NOT isEmpty(q) THEN
DECLARE value : STRING
value ← q.items[q.front]
q.front ← (q.front + 1) MOD q.capacity
q.size ← q.size - 1
RETURN value
ENDIF
ENDFUNCTION
Why circular is more efficient:
Linear queue wastes space - dequeued slots cannot be reused
Linear queue requires O(n) shifting when items are dequeued
Circular queue uses MOD operation to wrap pointers
All operations are O(1) - no shifting needed
Reuses empty slots at beginning when rear reaches end
8. A linked list stores data in nodes. Describe the structure of a node and explain how to traverse a linked list. [5 marks]
Answer:
Each node contains two parts: data and a pointer to the next node
Pointer stores the memory address of the next node
Last node has a null pointer (points to nothing)
A start pointer points to the first node
To traverse: Start at first node, follow pointers until null
While current ≠ NULL: process current.data, set current = current.next
Advantages: Dynamic size, efficient insertion/deletion at known positions, no wasted memory.
9. Describe three types of tree traversal (pre-order, in-order, post-order) and give an example of when each would be used. [6 marks]
Answer:
Pre-order (Root → Left → Right): Visit root first, then left subtree, then right subtree
Use: Copy a tree structure, produce prefix expressions
In-order (Left → Root → Right): Visit left subtree, then root, then right subtree
Use: Binary Search Tree produces sorted output
Post-order (Left → Right → Root): Visit left subtree, then right subtree, then root
Use: Delete a tree (delete children before parent), produce postfix expressions
All traversals have O(n) time complexity where n = number of nodes
10. Explain what Big-O notation measures. Compare O(n), O(log n), and O(n²) and give an example algorithm for each. [6 marks]
Answer:
Big-O notation measures time and space complexity - how algorithm scales with input size
It's hardware independent - measures steps/operations, not time in seconds
O(n) Linear: Steps grow linearly with input - example: Linear search, single loop