Computational thinking and algorithms

IntroComputational thinking and its four pillarsOften examined

Computational thinking (CT) is a problem-solving process based on the ideas of computer science. It lets us solve a big, complex problem by breaking it into small parts and then dealing with each part in a logical, step-by-step way. CT is not only for programmers. Doctors, engineers, business people and students use the same way of thinking in daily life.

Decomposition

Breaking a problem into smaller, more manageable parts. Example: building a website is split into designing, coding, backend set-up and testing.

Pattern recognition

Finding similarities or trends inside a problem or across similar problems, so that one solution can be reused. Example: noticing that every subject's marks are processed in the same way.

Abstraction

Focusing on the important information and ignoring details that do not matter for the problem. Example: a map of bus routes shows stops and routes, not every building.

Algorithm design

Writing clear, step-by-step instructions that solve the problem. Example: a fixed procedure that sorts numbers from smallest to largest.

At HSSC-II level, CT is used for two jobs: to design algorithms and to evaluate them for correctness, clarity and efficiency. The choice of data structure strongly affects how well a solution performs, so this unit first studies data structures (2.1) and then how to evaluate solutions (2.2).

2.1Data structuresOften examined

A program works with data: marks, names, prices, messages. How that data is arranged in memory decides how quickly we can find, add or remove an item. A data structure is a way of organising and storing data so that it can be accessed and modified efficiently.

Data structures give a framework for managing data in programs. They decide how data is arranged in memory and so affect the speed of operations such as insertion (adding), deletion (removing) and retrieval (finding or reading). For example, an array gives quick access to any element by its index, while a linked list makes it easy to add and remove elements. The right choice (array, linked list, stack, queue, tree or graph) depends on the needs of the application and the operations it performs most often.

2.1.1ArraysOften examined

An array is the simplest data structure. It stores a collection of elements of the same type (and size) in contiguous (side by side) memory locations. Each element is identified by an index. In Python and most languages the first index is 0.

Why arrays are efficient

• They need no extra data (metadata such as pointers) to store the elements, so no memory is wasted on links.
• Because the locations are contiguous, the address of any element can be calculated directly from its index. So any element can be reached in one step: this is called random (direct) access and takes $O(1)$ time.

For Fig. 2.1 with 1 byte per element: address of A[4] = 100 + 4 × 1 = 104, which holds E.

Limitations of arrays

• Fixed size: the size must be declared at the start. Resizing later is costly, because a new, larger array must be created and all elements shifted (copied) into it.
• Same type only: an array is not a good choice when the elements are of different types.
• Slow insertion and deletion in the middle: to insert at position $i$, all elements after $i$ must move one place to the right.

Types of arrays

One-dimensional (1-D) array

Elements of the same type stored in a single row (list). An element is reached with one index, for example marks[3].

Two-dimensional (2-D) array

Also called a matrix. Elements are stored as a table of rows and columns. An element is reached with two indexes, row and column, for example M[2][3].

Arrays in Python

Python's built-in list is used as an array. A 2-D array is a list of lists. (Python lists can hold mixed types, but for array work we keep one type.)

marks = [2, 4, 8, 12, 16, 18]          # 1-D array
print("marks[3] =", marks[3])          # direct access by index
marks[0] = 5                           # modify an element
print("Updated:", marks)

M = [[1, 2, 3, 4, 5],                  # 2-D array: 4 rows, 5 columns
     [6, 7, 8, 9, 10],
     [11, 12, 13, 14, 15],
     [16, 17, 18, 19, 20]]
print("M[2][3] =", M[2][3])            # row 2, column 3
for row in M:                          # traverse row by row
    print(row)

marks[3] = 12
Updated: [5, 4, 8, 12, 16, 18]
M[2][3] = 14
[1, 2, 3, 4, 5]
[6, 7, 8, 9, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20]

2.1.2Linked listsOften examined

In an array the elements sit next to each other. In a linked list they can be anywhere in memory; each element remembers where the next one is. A linked list is a data structure in which elements, called nodes, are connected using pointers. Each node stores a value and a pointer, which is the reference (memory address) of the next node in the sequence. The first node is reached through a pointer called head.

Advantages of linked lists

• Dynamic size: no need to declare the size at the start; the list grows and shrinks as nodes are added or removed.
• Easy insertion and deletion at any position: only a few pointers are changed; no elements are shifted as in an array.
• They can store different types of data, and memory is allocated only when a node is needed.

Disadvantages

• No random access: to reach the 50th node we must start at head and follow 49 links, so access takes $O(n)$ time.
• Extra memory is used for the pointer(s) in every node.

Singly linked list

The basic type. Each node has two parts: the data to be stored and a reference to the next node. The last node's next pointer is NULL (in Python, None) because it does not refer to any node. Traversal is possible in one direction only (forward).

Doubly linked list

More complex than a singly linked list but more useful. Each node has three parts: a reference to the previous node, the data, and a reference to the next node. The major advantage is that the list can be traversed in both directions. The prev of the first node and the next of the last node are NULL.

Circular linked list

A linked list in which the nodes form a circle (loop). The last node does not point to NULL; it points back to the first node. So a traversal never reaches NULL, and it must stop when it comes back to the starting node. A circular list can be made from either a singly or a doubly linked list. In a circular doubly linked list, the next of the last node points to the first node and the prev of the first node points to the last node.

A singly linked list in Python

class Node:
    def __init__(self, data):
        self.data = data      # value stored in the node
        self.next = None      # reference to the next node (None = NULL)

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        node = Node(data)
        node.next = self.head     # new node points to old first node
        self.head = node          # head now points to the new node

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            return
        cur = self.head
        while cur.next is not None:   # walk to the last node
            cur = cur.next
        cur.next = node

    def delete(self, value):
        cur, prev = self.head, None
        while cur is not None and cur.data != value:
            prev, cur = cur, cur.next
        if cur is None:
            return                    # value not found
        if prev is None:
            self.head = cur.next      # deleting the first node
        else:
            prev.next = cur.next      # bypass the deleted node

    def display(self):
        cur, items = self.head, []
        while cur is not None:
            items.append(str(cur.data))
            cur = cur.next
        print(" -> ".join(items + ["NULL"]))

ll = LinkedList()
for x in ["B", "C", "D"]:
    ll.append(x)
ll.insert_at_beginning("A")
ll.display()
ll.delete("C")
ll.display()

A -> B -> C -> D -> NULL
A -> B -> D -> NULL

2.1.3StacksOften examined

Think of a pile of plates. You put a new plate on the top and you also take a plate from the top. A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle: the element added most recently is the first one to be removed. All operations take place at one end, called the top. This makes a stack simple, and it is useful for algorithms that must manage tasks in a specific (reverse) order. A stack is memory efficient; its size may be fixed (array based) or dynamic (linked list based), depending on the implementation.

Push

Add a new element at the top of the stack.

Pop

Remove the existing element from the top of the stack (and return it).

Top (peek)

Return the top element without removing it.

IsEmpty

Check whether the stack is empty.

IsFull

Check whether the stack is full (for a fixed-size stack).

Stack in Python

class Stack:
    def __init__(self, capacity):
        self.items = []
        self.capacity = capacity

    def is_empty(self):
        return len(self.items) == 0

    def is_full(self):
        return len(self.items) == self.capacity

    def push(self, x):
        if self.is_full():
            print("Stack overflow: cannot push", x)
        else:
            self.items.append(x)          # add at the top (end of list)

    def pop(self):
        if self.is_empty():
            print("Stack underflow")
            return None
        return self.items.pop()           # remove from the top

    def top(self):
        return None if self.is_empty() else self.items[-1]

s = Stack(3)
s.push("A"); s.push("B"); s.push("C")
s.push("D")                               # stack is full
print("Stack:", s.items, " top =", s.top())
print("Popped:", s.pop())
print("Stack:", s.items, " top =", s.top())

Stack overflow: cannot push D
Stack: ['A', 'B', 'C']  top = C
Popped: C
Stack: ['A', 'B']  top = B

Applications of stacks

• Undo in text editors and the back button of a web browser (the last action or page is undone first).
• Function calls and recursion: the computer keeps a call stack; the most recent call finishes first.
• Reversing a word or list, and checking balanced brackets in expressions.
• Depth-first search (DFS) in graphs and trees uses a stack.

2.1.4QueuesOften examined

Think of students standing in a line at the canteen. The student who came first is served first, and new students join at the back. A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle: the first element added is the first one removed. Unlike a stack, a queue works at two ends: new elements are added at the rear (back or tail) and elements are removed from the front (head). It is useful for tasks that must be processed in the order they arrive.

Enqueue

Add a new element at the end (back, tail or rear) of the queue.

Dequeue

Remove the existing element from the start (front or head) of the queue.

Front (peek)

Return the front element without removing it.

IsEmpty

Check whether the queue is empty.

IsFull

Check whether the queue is full (for a fixed-size queue).

Queue in Python

Python's $\text{collections.deque}$ removes from the front in $O(1)$ time, so it is the usual way to build a queue.

from collections import deque

q = deque()
for job in ["Print A", "Print B", "Print C"]:
    q.append(job)                  # enqueue at the rear
print("Queue:", list(q))
print("Front:", q[0])              # peek at the front
print("Dequeued:", q.popleft())    # dequeue from the front
q.append("Print D")
print("Queue:", list(q))
print("Is empty?", len(q) == 0)

Queue: ['Print A', 'Print B', 'Print C']
Front: Print A
Dequeued: Print A
Queue: ['Print B', 'Print C', 'Print D']
Is empty? False

Applications of queues

• Scheduling: the CPU and printers serve jobs in the order they arrive (print queue).
• Buffering: keyboard input, video streaming and network packets are held in a queue until they are processed.
• Breadth-first search (BFS) in graphs uses a queue.
• Real life: customers at a bank counter, calls waiting at a call centre.

Stack versus queue

2.1.5Graphs

A road map shows cities joined by roads. A graph is a non-linear data structure made of nodes (vertices) connected to each other by edges. Graphs model complex relationships and networks: friends in a social network, cities and roads, computers in a network. They are used in network analysis, finding shortest paths (for example Dijkstra's algorithm) and checking connectivity.

Basic operations on a graph

Add vertex

Add a new node to the graph.

Add edge

Create a connection between two nodes.

Remove vertex or edge

Delete a node or an edge from the graph.

Traversal

Visit the nodes of the graph in a specific order, for example breadth-first search (BFS) or depth-first search (DFS).

Types of graphs

Connected graph

A graph in which at least one path exists between every pair of nodes. Starting from any node you can reach any other node.

Directed graph

A graph whose edges have a direction, shown by arrows. An edge from 1 to 0 lets you go from 1 to 0 but not back, unless there is also an edge from 0 to 1.

Storing and traversing a graph in Python

A graph is commonly stored as an adjacency list: for each vertex, a list of its neighbours. BFS visits nodes level by level using a queue; DFS goes as deep as possible first using a stack (here, recursion).

from collections import deque

graph = {                      # adjacency list of Fig. 2.13
    1: [3, 2],
    2: [1, 4, 6],
    3: [5, 1, 4],
    4: [3, 2],
    5: [3],
    6: [2],
}

def bfs(start):
    visited, order = {start}, []
    q = deque([start])
    while q:
        v = q.popleft()            # dequeue
        order.append(v)
        for n in graph[v]:
            if n not in visited:
                visited.add(n)
                q.append(n)        # enqueue
    return order

def dfs(v, visited=None):
    if visited is None:
        visited = []
    visited.append(v)
    for n in graph[v]:
        if n not in visited:
            dfs(n, visited)        # recursion uses the call stack
    return visited

print("BFS from 5:", bfs(5))
print("DFS from 5:", dfs(5))

BFS from 5: [5, 3, 1, 4, 2, 6]
DFS from 5: [5, 3, 1, 2, 4, 6]

2.1.6Trees and binary search treesOften examined

A family tree or the folders on your computer have one item at the top that branches into more items below. A tree is a non-linear data structure that represents a hierarchy of nodes. Each node consists of a value and pointers to its children.

Root

The topmost node of the tree. It has no parent.

Parent and child

Directly connected nodes form a parent-child relationship: the higher node is the parent and the lower node is the child.

Leaf node

A node that has no child.

Edge

The link (relationship) between two nodes.

Siblings

Nodes that have the same parent.

Level

The distance of a node from the root; the root is at level 0.

Subtree

A node together with all of its descendants; it is itself a tree.

Height

The number of edges on the longest path from the root to a leaf.

Trees are important for understanding complex relationships between data, and they are the base of many advanced data structures. In computer science, the directory (folder) structure of an operating system and the tag structure of an HTML page are the best examples of trees.

Basic operations on trees

Insertion

Add a new node at a specified location in the tree.

Deletion

Remove an existing node.

Search

Find a specific node in the tree.

Traversal

Visit all nodes of the tree in a specific order (in-order, pre-order, post-order).

Binary tree and binary search tree (BST)

A binary tree is a tree in which every node has at most two children, called the left child and the right child. A binary search tree (BST) is a binary tree with an ordering rule: for every node, all keys in its left subtree are smaller than the node's key and all keys in its right subtree are larger. This rule is what makes searching fast: at each node we compare once and go only left or only right, like binary search on a sorted list.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)     # smaller keys go left
    else:
        root.right = insert(root.right, key)   # larger keys go right
    return root

def search(root, key):
    steps = 0
    while root is not None:
        steps += 1
        if key == root.key:
            return True, steps
        root = root.left if key < root.key else root.right
    return False, steps

root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, k)
print("Search 60:", search(root, 60))
print("Search 45:", search(root, 45))

Search 60: (True, 3)
Search 45: (False, 3)

2.1.6Tree traversalOften examined

Tree traversal means visiting every node of a tree exactly once in a systematic order. There are several methods and each has a different purpose. For binary trees the three common depth-first methods differ only in when the root is visited: before, between or after its two subtrees.

In-order traversal (Fig. 2.17)

Start at root 1 and go down the left side to the leftmost node 4. Visit 4, then its parent 2, then 2's right child 5. The left subtree of 1 is finished, so visit 1, then traverse its right subtree: 3 has no left child, so visit 3, then 6. Order: 4, 2, 5, 1, 3, 6. In-order is often used with binary search trees, because it visits the keys in ascending (sorted) order.

Pre-order traversal (Fig. 2.18)

Visit the root 1 first, then the whole left subtree in pre-order (2, then 4, then 5), then the right subtree (3, then 6). Order: 1, 2, 4, 5, 3, 6. Pre-order is useful when we must work with a node before its children, for example to copy a tree or to print a folder before the files inside it.

Post-order traversal (Fig. 2.19)

Finish the left subtree (4, 5, then 2), then the right subtree (6, then 3), and visit the root 1 last. Order: 4, 5, 2, 6, 3, 1. Post-order is used for deleting nodes or freeing memory, because it processes the children before their parent; it is also used to find the total size of a folder.

Traversals in Python

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def inorder(n):
    if n:
        inorder(n.left); print(n.key, end=" "); inorder(n.right)

def preorder(n):
    if n:
        print(n.key, end=" "); preorder(n.left); preorder(n.right)

def postorder(n):
    if n:
        postorder(n.left); postorder(n.right); print(n.key, end=" ")

# tree of Fig. 2.17 to 2.19
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print("In-order:  ", end=" "); inorder(root); print()
print("Pre-order: ", end=" "); preorder(root); print()
print("Post-order:", end=" "); postorder(root); print()

In-order:   4 2 5 1 3 6 
Pre-order:  1 2 4 5 3 6 
Post-order: 4 5 2 6 3 1 

2.1How data structures support computational thinking

• Problem decomposition: different data structures help break a problem into manageable parts, which makes algorithms easier to design and implement.
• Efficiency considerations: they show trade-offs between operations, for example fast access (array) versus fast insertion (linked list), which helps us choose the most suitable structure for a problem.
• Algorithmic thinking: understanding these structures helps in developing and analysing algorithms, and improves problem solving by choosing the right tool for each task.

So data structures are not just containers for data; they shape the way we think about a problem and design its algorithm.

2.2, 2.2.1Evaluating computational solutions: correctnessOften examined

There is usually more than one algorithm for a problem. To decide which one is better we evaluate it against three criteria: correctness (does it give the right answer?), clarity (is it easy to understand?) and efficiency (does it use little time and memory?).

Correctness

An algorithm is correct if it produces the expected output for all valid inputs. To check correctness we run it on many test cases that cover different situations, including edge cases: unusual or boundary inputs such as an empty list, a list with one element, repeated values, negative numbers or zero.

def bubble_sort(arr):
    a = arr[:]                          # work on a copy
    n = len(a)
    for i in range(n - 1):              # passes
        for j in range(n - 1 - i):      # compare neighbours
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]   # swap
    return a

tests = [
    ([5, 2, 9, 1, 5, 6], [1, 2, 5, 5, 6, 9]),   # book's test case
    ([], []),                                   # edge case: empty
    ([7], [7]),                                 # edge case: one element
    ([3, 2, 1], [1, 2, 3]),                     # reverse order
    ([-4, 0, -9, 2], [-9, -4, 0, 2]),           # negative numbers
]
for data, expected in tests:
    result = bubble_sort(data)
    print(data, "->", result, "PASS" if result == expected else "FAIL")

[5, 2, 9, 1, 5, 6] -> [1, 2, 5, 5, 6, 9] PASS
[] -> [] PASS
[7] -> [7] PASS
[3, 2, 1] -> [1, 2, 3] PASS
[-4, 0, -9, 2] -> [-9, -4, 0, 2] PASS

2.2.2Clarity

An algorithm is clear if its steps are logically structured and easy to understand. Clear code is easier to check, debug, modify and share with other programmers.

How to make an algorithm clear

• Use descriptive names for variables and functions (total_marks, not tm).
• Order the steps logically, one task per step.
• Add documentation and comments that explain what the code does.
• Use proper indentation and simple, standard constructs instead of clever one-line tricks.

Example: two Python functions that calculate the factorial of a number.

# Case 1: clear code
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

# Case 2: less clear code
def fct(n):
    return 1 if n == 0 else n * fct(n - 1)

print(factorial(5), fct(5))

120 120

Both give 120 for $5!$, so both are correct. The first case is easier to read: the name factorial tells what the function does and the condition if n == 0 is written clearly on its own line. The second case uses a short name (fct) and a ternary operator on one line; it is valid but less understandable for someone new to the code.

2.2.3Efficiency: time complexity, space complexity and Big OOften examined

Efficiency refers to how well an algorithm uses computer resources, mainly time and memory. It is usually expressed using Big O notation, for example $O(n)$, $O(\log n)$, $O(n^2)$. Here $n$ is the input size: the size of the problem, such as the number of items in a list.

Time complexity

A measure of the execution time of an algorithm with respect to the size of its input. It is estimated by counting the basic steps (comparisons, assignments) the algorithm performs as $n$ grows, not by using a stopwatch, because real time depends on the computer.

Space complexity

A measure of the amount of memory an algorithm uses with respect to the size of its input (extra variables, arrays, recursion stack).

Worst case

The input that makes the algorithm do the most work. For searching an array one by one, the worst case is when the item is at the last index or not present.

Big O notation

A notation that gives an upper bound of an algorithm's running time or space as the input grows. It describes the efficiency under the most challenging (worst-case) conditions and ignores constants and smaller terms.

Common Big O notations

import math
print(f"{'n':>6} {'log2 n':>7} {'n log2 n':>9} {'n^2':>10}")
for n in [10, 100, 1000, 10000]:
    print(f"{n:>6} {math.log2(n):>7.1f} {n * math.log2(n):>9.0f} {n * n:>10}")

     n  log2 n  n log2 n        n^2
    10     3.3        33        100
   100     6.6       664      10000
  1000    10.0      9966    1000000
 10000    13.3    132877  100000000

The table shows why efficiency matters for large inputs: for 10,000 items an $O(\log n)$ algorithm needs about 13 steps, an $O(n)$ algorithm 10,000 steps and an $O(n^2)$ algorithm 100 million steps.

2.2.3Example 1: binary searchOften examined

Binary search locates a target value in a sorted array by repeatedly dividing the search interval in half. It is a divide and conquer algorithm.

Algorithm steps

1. Start by examining the number in the centre (middle) of the list.
2. Check whether this middle number equals the one we are looking for.
3. If it matches, we have located the number.
4. If the target is smaller (on the left part of the list), repeat the process on the left half, ignoring the right half.
5. If the target is larger (in the right half), ignore the left half and repeat the process on the right half.
6. Continue until the number is found or the remaining part of the list is empty (the number is not in the list).

Trace

Search for 23 in the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indexes 0 to 9). low and high mark the ends of the current range; mid = (low + high) // 2.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2        # middle index
        if arr[mid] == target:
            return mid                 # found
        elif target < arr[mid]:
            high = mid - 1             # search left half
        else:
            low = mid + 1              # search right half
    return -1                          # not found

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("23 at index", binary_search(data, 23))
print("50 at index", binary_search(data, 50))

# correctness tests (book: key 3 in [1, 2, 3, 4, 5] gives index 2)
tests = [([1, 2, 3, 4, 5], 3, 2), ([1, 2, 3, 4, 5], 1, 0),
         ([1, 2, 3, 4, 5], 5, 4), ([1, 2, 3, 4, 5], 6, -1),
         ([], 3, -1), ([7], 7, 0)]
for arr, key, expected in tests:
    r = binary_search(arr, key)
    print(arr, key, "->", r, "PASS" if r == expected else "FAIL")

23 at index 5
50 at index -1
[1, 2, 3, 4, 5] 3 -> 2 PASS
[1, 2, 3, 4, 5] 1 -> 0 PASS
[1, 2, 3, 4, 5] 5 -> 4 PASS
[1, 2, 3, 4, 5] 6 -> -1 PASS
[] 3 -> -1 PASS
[7] 7 -> 0 PASS

Space complexity

The book gives the space complexity of binary search as $O(\log n)$ (logarithmic space). This is for the recursive version: each recursive call adds a new frame to the call stack, and in the worst case the number of recursive calls equals the number of times $n$ can be halved, ${\log }_{2}n$.

def binary_search_rec(arr, target, low, high, depth=1):
    if low > high:
        return -1, depth
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid, depth
    if target < arr[mid]:
        return binary_search_rec(arr, target, low, mid - 1, depth + 1)
    return binary_search_rec(arr, target, mid + 1, high, depth + 1)

arr = list(range(1, 1025))           # 1024 sorted numbers
print("(index, recursion depth):", binary_search_rec(arr, 1024, 0, len(arr) - 1))

(index, recursion depth): (1023, 11)

2.2.3Example 2: linear searchOften examined

In linear (sequential) search each element of the array is examined one by one until the target value is found or the end of the array is reached. It works on unsorted as well as sorted data.

Algorithm steps

1. Start at the beginning of the array and examine each element one by one.
2. Compare the target value with each element of the array.
3. The search is completed when the target value matches an element.
4. If the array ends and no match is found, conclude that the target is not in the array.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i          # found at index i
    return -1                 # not found

items = [34, 7, 23, 32, 5, 62]
print("23 at index", linear_search(items, 23))
print("62 at index", linear_search(items, 62), "(worst case: last element)")
print("10 at index", linear_search(items, 10))

23 at index 2
62 at index 5 (worst case: last element)
10 at index -1

Time complexity: O(n)

The number of operations grows linearly with the input size. For an array of $n$ elements we may check the first, second, and so on up to the $n$th element. In the worst case (target at the last index or not present) every one of the $n$ elements is examined, so the time complexity is $O(n)$. (Best case: target at the first index, 1 comparison.)

Space complexity: O(1)

Linear search uses a fixed amount of extra memory whatever the size of the input: only a few variables for the current index and the target. So its space complexity is constant, $O(1)$.

2.2.1, 2.2.3Sorting algorithms: bubble sort and merge sort

Sorting algorithms arrange data in a particular order, for example ascending. The book uses bubble sort to explain correctness and names merge sort and quick sort as $O(n\log n)$ algorithms. Comparing them is a good exercise in evaluating solutions.

Bubble sort

Compare each pair of neighbouring elements and swap them if they are in the wrong order. One pass moves the largest element to the end; repeat $n-1$ passes. It uses two nested loops, so it makes about $n(n-1)/2$ comparisons: time complexity $O(n^2)$. It sorts in place, so extra space is $O(1)$. It is very easy to understand and code (high clarity) but slow for large lists.

Merge sort

A divide and conquer algorithm: (1) divide the list into two halves, (2) sort each half by merge sort (recursively), (3) merge the two sorted halves into one sorted list. The list can be halved ${\log }_{2}n$ times and each level of merging handles all $n$ elements, so the time complexity is $O(n\log n)$. It needs an extra list for merging, so space is $O(n)$. It is harder to understand than bubble sort because of recursion.

def merge_sort(a):
    if len(a) <= 1:
        return a                          # a list of 0 or 1 items is sorted
    mid = len(a) // 2
    left = merge_sort(a[:mid])            # divide and sort each half
    right = merge_sort(a[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):   # merge two sorted halves
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
print(merge_sort(["Zara", "Ali", "Hina", "Bilal"]))

[3, 9, 10, 27, 38, 43, 82]
['Ali', 'Bilal', 'Hina', 'Zara']

Quick sort

Quick sort picks a pivot element, places smaller elements to its left and larger ones to its right (partition), then sorts the two parts recursively. Its average time is $O(n\log n)$ (worst case $O(n^2)$ with bad pivots).

2.2.4Case studies: evaluating two algorithmsOften examined

The book evaluates complete solutions under four headings: algorithm, efficiency (time and space complexity), clarity and correctness. The exercise asks you to do the same, so learn this pattern.

Problem 1: greatest common divisor (GCD)

Problem statement: given two integers, find their greatest common divisor. Solution: the Euclidean algorithm.

def gcd(a, b):
    while b != 0:
        print(f"a = {a}, b = {b}, a % b = {a % b}")
        a, b = b, a % b        # both updated at the same time
    return a

print("GCD =", gcd(48, 18))

a = 48, b = 18, a % b = 12
a = 18, b = 12, a % b = 6
a = 12, b = 6, a % b = 0
GCD = 6

• Efficiency: time complexity $O(\log \min (a,b))$, because the remainder shrinks quickly (it at least halves every two steps); space complexity $O(1)$, as only a few variables are used.
• Clarity: the algorithm is elegant and clear: a simple loop with one assignment.
• Correctness: it is based on the mathematical fact $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$ and $\gcd (a,0)=a$, so it always gives the right GCD.

Problem 2: count the vowels in a string

Problem statement: for an input string, count the number of vowels. Solution: simple iteration.

def count_vowels(text):
    count = 0
    for ch in text.lower():          # lower() also counts capital vowels
        if ch in "aeiou":
            count += 1
    return count

print(count_vowels("Computational Thinking"))
print(count_vowels(""))              # edge case: empty string

8
0

• Efficiency: time complexity $O(n)$, where $n$ is the length of the string (each character is checked once); space complexity $O(1)$, as only a counter is used.
• Clarity: simple and clear: basic iteration and a conditional check.
• Correctness: it counts the vowels correctly by examining every character; converting to lower case makes capital vowels count too.

SummaryTypes of algorithms (unit summary)

The unit summary lists the main families of algorithms. Know one example of each for MCQs.

def fibonacci(n):
    fib = [0, 1]                         # store solutions of subproblems
    for i in range(2, n + 1):
        fib.append(fib[i - 1] + fib[i - 2])   # reuse stored answers
    return fib[n]

print([fibonacci(i) for i in range(10)])

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Formula sheet

Key terms

Computational thinking

A problem-solving process based on computer science principles: decomposition, pattern recognition, abstraction and algorithm design.

Decomposition

Breaking a problem into smaller, manageable parts.

Pattern recognition

Identifying similarities or trends to simplify a problem.

Abstraction

Focusing on important information and ignoring irrelevant details.

Algorithm

A finite set of clear, step-by-step instructions to solve a problem.

Data structure

A way of organising and storing data so that it can be accessed and modified efficiently.

Array

A collection of elements of the same type in contiguous memory locations, each reached by an index.

Index

The position number of an element in an array, starting from 0.

2-D array (matrix)

An array arranged in rows and columns; an element needs two indexes.

Linked list

A linear data structure of nodes joined by pointers; each node holds data and the address of the next node.

Node

One element of a linked list, tree or graph, holding data and link(s).

Pointer (reference)

A value that holds the memory address of another node.

Head

The pointer to the first node of a linked list.

NULL

A special value meaning a pointer refers to no node.

Singly linked list

A linked list whose nodes have data and a next pointer; traversal is forward only.

Doubly linked list

A linked list whose nodes have prev, data and next; traversal in both directions.

Circular linked list

A linked list in which the last node points back to the first node.

Stack

A LIFO data structure where insertion and deletion happen at the top.

LIFO

Last-In, First-Out: the element added last is removed first.

Push / Pop

Add an element to / remove an element from the top of a stack.

Stack overflow / underflow

Pushing onto a full stack / popping from an empty stack.

Queue

A FIFO data structure where elements join at the rear and leave from the front.

FIFO

First-In, First-Out: the element added first is removed first.

Enqueue / Dequeue

Add an element at the rear / remove an element from the front of a queue.

Graph

A non-linear data structure of vertices (nodes) connected by edges.

Vertex / Edge

A node of a graph / a connection between two nodes.

Connected graph

A graph with at least one path between every pair of vertices.

Directed graph

A graph whose edges have a direction.

Tree

A non-linear hierarchical data structure of nodes with a single root.

Root

The topmost node of a tree.

Leaf node

A tree node with no children.

Siblings

Nodes with the same parent.

Subtree

A node together with all its descendants.

Binary tree

A tree in which each node has at most two children.

Binary search tree (BST)

A binary tree where left-subtree keys are smaller and right-subtree keys are larger than the node.

Tree traversal

Visiting every node of a tree once in a systematic order.

In-order traversal

Left subtree, root, right subtree.

Pre-order traversal

Root, left subtree, right subtree.

Post-order traversal

Left subtree, right subtree, root.

BFS / DFS

Breadth-first search (level by level, uses a queue) / depth-first search (as deep as possible, uses a stack).

Correctness

An algorithm's ability to give the expected output for all valid inputs.

Edge case

An unusual or boundary input, such as an empty list or a single element.

Clarity

How logically structured and easy to understand an algorithm is.

Efficiency

How well an algorithm uses resources such as time and memory.

Time complexity

How the running time of an algorithm grows with input size.

Space complexity

How the memory used by an algorithm grows with input size.

Big O notation

Notation giving an upper bound (usually worst case) on the growth of time or space with input size.

Worst case

The input that makes an algorithm do the most work.

Binary search

Searching a sorted array by repeatedly halving the search range; O(\log n).

Linear search

Checking elements one by one; O(n).

Divide and conquer

Solving a problem by splitting it into smaller parts, solving them and combining the results (binary search, merge sort).

Greedy algorithm

An algorithm that makes the best choice at each step (Huffman coding).

Dynamic programming

Solving overlapping subproblems once and storing their answers (Fibonacci numbers).

Backtracking

Trying choices and undoing them at dead ends (N-Queens, Sudoku).

FBISE 2026 questions

Questions from the FBISE HSSC-II 2026 (1st Annual) papers that belong to this unit, answered the way an examiner expects.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def preorder(n):  return [n.key] + preorder(n.left) + preorder(n.right) if n else []
def postorder(n): return postorder(n.left) + postorder(n.right) + [n.key] if n else []

root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print("Pre-order: ", preorder(root))
print("Post-order:", postorder(root))

Pre-order:  [1, 2, 4, 5, 3, 6]
Post-order: [4, 5, 2, 6, 3, 1]

digits = [4, 0, 9, 6]
total = 0
for d in digits:        # the loop runs n times
    total += d
print("Sum =", total)

Sum = 19

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def inorder(n):  return inorder(n.left) + [n.key] + inorder(n.right) if n else []
def preorder(n): return [n.key] + preorder(n.left) + preorder(n.right) if n else []

root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
print("In-order: ", inorder(root))
print("Pre-order:", preorder(root))

In-order:  [4, 2, 5, 1, 6, 3, 7]
Pre-order: [1, 2, 4, 5, 3, 6, 7]

Exam focus

1. Tree traversals: in-order, pre-order and post-order with the order of operations and an example tree. (long)
   Came as the 5-mark Section C question in both 2026 sets (Set B Q.4 OR, Set D Q.3 OR) and as an MCQ.
   Go to answer
2. Differentiate between stack and queue with real-life examples; purposes of push, pop, top and enqueue, dequeue, front. (short)
   Four 2026 short questions and an MCQ came from stacks and queues.
   Go to answer
3. What is a linked list? Advantages; singly versus doubly; circular linked list. (short)
   Asked in both 2026 sets (Set B Q.2 (iii), Set D Q.2 (ix)) and as an MCQ.
   Go to answer
4. What is an array? Advantages and its two types (1-D and 2-D). (short)
   Asked in both 2026 sets (Set B Q.2 (ix), Set D Q.2 (ii)).
   Go to answer
5. Difference between time complexity and space complexity; Big O classes with examples. (short)
   Set B Q.2 (vi) OR; Big O is the core of evaluating efficiency.
   Go to answer
6. Correctness of an algorithm with an example (test cases and edge cases). (short)
   Set D Q.2 (viii) OR; correctness, clarity and efficiency are the unit's second SLO.
   Go to answer
7. Time and space complexity of case-study problems (sum of digits, factorial, largest, prime, average, GCD, vowels). (short)
   Set D Q.2 (xi) asked exactly this type; the book's SRQs follow the same pattern.
   Go to answer
8. Binary search: steps, program, trace and derivation of O(\log n); compare with linear search. (long)
   The key algorithm of the unit; MCQs on its complexity are common.
   Go to answer
9. Bubble sort versus merge sort for a large list. (long)
   Book ERQ 1; tests time complexity and clarity together.
   Go to answer
10. Tree terms (root, leaf, parent, child, siblings, level) and the BST property. (mcq)
    Leaf node was a 2026 MCQ; BSTs are named in the SLOs.
    Go to answer
11. Four pillars of computational thinking with examples. (short)
    Opening topic of the unit and a source of scenario MCQs.
    Go to answer