Computational Thinking and Problem-Solving

Computational Thinking

Computational thinking is a structured approach to solving problems in a way that can be understood and executed by a computer. The IB syllabus identifies four key thinking approaches.

Four Computational Thinking Approaches

Thinking abstractly — identifying and extracting the essential features of a problem while ignoring irrelevant detail. For example, a map application abstracts road geometry but omits the colour of buildings.

Thinking ahead — planning what outputs are needed before designing the process; identifying pre-conditions, post-conditions, and the order in which steps must happen. For example, a sorting algorithm must consider that its output must satisfy a specific ordering property before a step is written.

Thinking procedurally — breaking a complex task into a sequence of clearly ordered steps that, when followed, produce the desired result. For example, writing a recipe as numbered steps.

Thinking concurrently — identifying parts of a problem that can be done simultaneously (in parallel) rather than sequentially. For example, a search engine crawls multiple web pages at the same time rather than one after another.

Flowcharts

A flowchart is a visual representation of an algorithm, using standardised symbols to show the sequence of steps, decisions, and loops. Flowcharts help communicate an algorithm’s logic before writing code or pseudocode.

Standard Flowchart Symbols

Reading a Flowchart

Execution flows from the Start terminal downward (or in the direction of arrows). At a diamond (decision), the flow splits: one path for the “Yes” (true) branch and one for the “No” (false) branch. Loops are created by having a flow line loop back to an earlier point.

input A
input B
if A > B then
    output A
else
    output B
end if

Problem Decomposition and Modular Design

Problem decomposition means breaking a large, complex problem into smaller, more manageable sub-problems. Each sub-problem can then be solved independently and the solutions combined.

Modular design applies decomposition to programming: the solution is built as a collection of modules (procedures, functions, methods), each responsible for one specific task.

Benefits of modular design:

• Each module can be written, tested, and debugged independently (unit testing)
• Modules can be reused across different programs
• Large programs can be developed by teams working on different modules simultaneously
• Easier to maintain — changing one module does not require rewriting others, provided the interface (inputs and outputs) stays the same
• Makes programs easier to read and understand

IB Pseudocode Conventions

IB Computer Science uses a standardised pseudocode notation in all exams. You must use this exact syntax in Paper 1 and Paper 2 answers — markers will not accept general-purpose code or other pseudocode styles.

Variables and Assignment

count ← 0
name ← "Alice"
total ← total + 5

The ← symbol means “is assigned the value of”. The right-hand side is evaluated first, then the result is stored in the variable on the left.

Input and Output

input name
output "Hello, ", name
output score

Conditionals

if score >= 50 then
    output "Pass"
else
    output "Fail"
end if

Multi-branch:

if grade = "A" then
    output "Excellent"
else if grade = "B" then
    output "Good"
else
    output "Acceptable"
end if

Loops

Count-controlled loop (from/to):

loop count from 1 to 10
    output count
end loop

Condition-controlled loop:

loop while answer ≠ "quit"
    input answer
end loop

Arrays

IB pseudocode uses 1-based indexing — the first element is arr[1], and an array of N elements runs from arr[1] to arr[N]. A 1D array named scores with 5 elements:

scores[1] ← 85
scores[5] ← 72
output scores[2]

Methods and Procedures

METHOD greet(name)
    output "Hello, ", name
END METHOD

METHOD add(a, b)
    return a + b
END METHOD

Call a method: greet("Alice") or result ← add(3, 5)

Algorithm Design — Searching

A searching algorithm locates a specific item within a collection of data. The two algorithms required for IB SL are linear search and binary search.

Linear Search

Examines each element of the array in sequence from the first to the last until the target is found or all elements have been checked.

Pre-condition: None — the array does not need to be sorted.

Pseudocode:

METHOD linearSearch(arr, target)
    found ← false
    index ← 1
    loop while index <= length(arr) and found = false
        if arr[index] = target then
            found ← true
        else
            index ← index + 1
        end if
    end loop
    if found = true then
        return index
    else
        return -1
    end if
END METHOD

Time complexity (concept): In the worst case, every element is examined — $n$ comparisons for an array of $n$ elements. This is called linear or $O(n)$ complexity.

Binary Search

Repeatedly halves the search space by comparing the target to the middle element. Requires the array to be sorted beforehand.

Pre-condition: Array must be sorted in ascending order.

Pseudocode:

METHOD binarySearch(arr, target)
    low ← 1
    high ← length(arr)
    found ← false
    loop while low <= high and found = false
        mid ← (low + high) div 2
        if arr[mid] = target then
            found ← true
        else if arr[mid] < target then
            low ← mid + 1
        else
            high ← mid - 1
        end if
    end loop
    if found = true then
        return mid
    else
        return -1
    end if
END METHOD

Time complexity (concept): Each step halves the remaining elements. For $n$ elements, at most $\log_2 n$ comparisons are needed — much faster than linear search for large arrays.

Algorithm Design — Sorting

A sorting algorithm rearranges the elements of an array into a specified order (typically ascending). Two algorithms are required for IB SL.

Bubble Sort

Repeatedly compares adjacent pairs of elements and swaps them if they are in the wrong order. After each full pass, the largest unsorted element “bubbles” to its correct position at the end.

Pseudocode:

METHOD bubbleSort(arr)
    n ← length(arr)
    loop i from 1 to n - 1
        loop j from 1 to n - i
            if arr[j] > arr[j + 1] then
                temp ← arr[j]
                arr[j] ← arr[j + 1]
                arr[j + 1] ← temp
            end if
        end loop
    end loop
END METHOD

Selection Sort

Finds the minimum element in the unsorted portion of the array and swaps it into the next sorted position. Repeats until the entire array is sorted.

Concept (pseudocode):

METHOD selectionSort(arr)
    n ← length(arr)
    loop i from 1 to n - 1
        minIndex ← i
        loop j from i + 1 to n
            if arr[j] < arr[minIndex] then
                minIndex ← j
            end if
        end loop
        if minIndex ≠ i then
            temp ← arr[i]
            arr[i] ← arr[minIndex]
            arr[minIndex] ← temp
        end if
    end loop
END METHOD

Key difference from bubble sort: Selection sort makes at most $n-1$ swaps (one per pass); bubble sort may make many more swaps. However, both make $O(n^2)$ comparisons.

Trace Tables

A trace table is a tool for manually simulating the execution of an algorithm, tracking the value of each variable at each step. Trace tables are used in IB exams to demonstrate understanding of algorithm execution.

How to Construct a Trace Table

1. Identify all variables used in the algorithm
2. Create a column for each variable (and one for any output)
3. Execute the algorithm one line at a time, recording each change
4. Record only the values that change at each step; leave unchanged cells blank

METHOD findMax(arr)
    max ← arr[1]
    loop i from 2 to length(arr)
        if arr[i] > max then
            max ← arr[i]
        end if
    end loop
    return max
END METHOD

Collection Types

The IB syllabus requires understanding of four abstract data structures and their basic operations.

Arrays

An array is an ordered, fixed-size collection of elements of the same type, accessed by index.

• Access any element directly by index: $O(1)$
• Inserting or deleting in the middle is slow (requires shifting elements)
• IB arrays are 1-based: arr[1] is the first element, arr[N] is the last in an N-element array

2D Arrays

A 2D array (two-dimensional array) is an array of arrays — a grid of elements arranged in rows and columns. It is used to represent matrices, game boards, tables, and image pixel grids.

In IB pseudocode, a 2D array is accessed using two indices: grid[row][col]. Both indices are 1-based.

grid[1][1] ← 5
grid[2][3] ← 9
output grid[1][1]

Traversing a 2D array (reading every element):

METHOD print2DArray(grid, rows, cols)
    loop i from 1 to rows
        loop j from 1 to cols
            output grid[i][j]
        end loop
    end loop
END METHOD

METHOD sumGrid(grid)
    total ← 0
    loop i from 1 to 3
        loop j from 1 to 3
            total ← total + grid[i][j]
        end loop
    end loop
    return total
END METHOD

Stacks

A stack is a Last-In, First-Out (LIFO) collection. Think of a stack of plates — you add and remove only from the top.

Real-world uses: undo/redo in editors, call stack in program execution, browser back button history.

Queues

A queue is a First-In, First-Out (FIFO) collection. Think of a line at a checkout — the first person to join is the first to be served.

Real-world uses: print job queues, CPU scheduling, network packet queues.

Linked Lists

A linked list is a dynamic collection of nodes, where each node stores a data value and a pointer (reference) to the next node. Unlike arrays, linked lists do not require contiguous memory.

• Advantage: Inserting or deleting a node requires only updating pointers — no shifting of elements
• Disadvantage: Accessing element $n$ requires traversing from the head — $O(n)$ access time
• The last node’s pointer is null (or NIL), indicating the end of the list

HL Abstract Data Structures

Binary Trees

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. The topmost node is the root; nodes with no children are leaves.

Binary Search Tree (BST): A special binary tree where, for every node:

• All values in the left subtree are less than the node’s value
• All values in the right subtree are greater than the node’s value

This property enables efficient searching, insertion, and deletion.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Three traversal orders for binary trees:

Searching in a BST:

1. Start at the root
2. If the target equals the current node, found
3. If the target is less, go left; if greater, go right
4. Repeat until found or reach a null pointer (not present)

Average time complexity: $O(\log n)$ for a balanced BST — each step halves the remaining search space, just like binary search on an array.

HL Recursion

Recursion is a programming technique where a function calls itself as part of its own definition. A recursive function must have:

1. Base case — a condition under which the function returns a result without calling itself again (prevents infinite recursion)
2. Recursive case — the function calls itself with a simpler or smaller version of the problem

How Recursion Works

Each recursive call creates a new stack frame on the call stack, storing the local variables and the return address for that call. When the base case is reached, the stack unwinds — each frame returns its result to the caller below it.

METHOD factorial(n)
    if n = 0 then
        return 1
    else
        return n * factorial(n - 1)
    end if
END METHOD

Recursion vs iteration:

HL Big-O Notation

Big-O notation describes the time complexity of an algorithm — how the number of operations grows as the input size $n$ increases. It focuses on the dominant term as $n$ becomes large, ignoring constants and lower-order terms.

Common Complexity Classes

Analysing Algorithm Complexity

• Single loop over $n$ elements: $O(n)$
• Nested loop (loop inside a loop), each running $n$ times: $O(n^2)$
• Halving the search space each step: $O(\log n)$
• Fixed number of steps regardless of input: $O(1)$

Standard Algorithms

Beyond searching and sorting, the IB syllabus requires students to be able to write or trace algorithms for these common tasks.

Finding Minimum and Maximum

METHOD findMin(arr)
    min ← arr[1]
    loop i from 2 to length(arr)
        if arr[i] < min then
            min ← arr[i]
        end if
    end loop
    return min
END METHOD

The maximum algorithm is identical but uses > and a variable named max.

Counting Occurrences

METHOD countOccurrences(arr, target)
    count ← 0
    loop i from 1 to length(arr)
        if arr[i] = target then
            count ← count + 1
        end if
    end loop
    return count
END METHOD

Video Resources

Practice Questions

METHOD sumArray(arr)
    total ← 0
    loop i from 1 to length(arr)
        total ← total + arr[i]
    end loop
    output total
END METHOD

METHOD linearSearch(arr, target)
    found ← false
    loop i from 1 to length(arr)
        if arr[i] = target then
            found ← true
        end if
    end loop
    return found
END METHOD