🤖 IBDP Computer Science HL: Algorithm

Revision Guide
1. Data Structures: Arrays (Static)
1.1 Topic Overview
An Array is a linear, static data structure that stores a collection of elements of the same data type in
contiguous memory locations. Each element is accessed via an index.

Concept Purpose Analogy Complexity IB Command

Term Focus

Array Store multiple A set of O(1) for direct Outline the

related data labeled access structure,
items of the pigeonholes (indexing). explain index
same type under or mailboxes. addressing.
a single variable
name.

Traversal Systematically Reading O(n) Construct a

visit every every book on loop for
element once. a single shelf. traversal.

Multi-D Store tabular A O(1) for direct Explain

Array data or matrices. spreadsheet access indexing and
(rows and array[r][c]. storage
columns). (row/column-m
ajor).

1.2 Traversal and Searching Pseudocode

Linear Search
Used on unsorted or sorted arrays. It checks every element sequentially until the target is found.

Algorithm Big-O Complexity Optimization Note

Name

Linear Search Best: O(1) (First Early exit as soon as the element is
element) found.
 Worst/Average: O(n)

Code snippet

FUNCTION LinearSearch(data, target) RETURNS INTEGER

// data: The array to search, target: The value being sought

n ← LENGTH(data)

FOR i ← 0 TO n - 1 DO // Traverses the array from start to end

IF data[i] = target THEN

RETURN i // Found: Return the index immediately (Early Exit)

END IF

END FOR

RETURN -1 // Not found: Return a special value (e.g., -1)

END FUNCTION

Binary Search
Requires the array to be sorted. It repeatedly halves the search interval.

Algorithm Big-O Complexity Optimization Note

Name

Binary Search Best: O(1) Requires the array to be sorted first

(O(n log n) cost).

Worst/Average: O(log
n)

Code snippet

FUNCTION BinarySearch(data, target) RETURNS INTEGER

// data MUST be sorted

low ← 0 // Index of the first element

high ← LENGTH(data) - 1 // Index of the last element

 WHILE low <= high DO // Continue searching while a valid range exists

mid ← FLOOR((low + high) / 2) // Calculate the middle index (integer division)

IF data[mid] = target THEN

RETURN mid // Found the target

ELSE IF data[mid] < target THEN

low ← mid + 1 // Target must be in the upper half

ELSE

high ← mid - 1 // Target must be in the lower half

END IF

END WHILE

RETURN -1 // Not found

END FUNCTION

1.3 Insertion and Deletion Logic

Insertion and deletion in a static array typically involve shifting other elements, making them O(n) operations.

Operation Logic Common Mistake

Insertion Start at the last element and shift Incorrect loop range, leading to
backwards (j to j-1) to create a overwriting the last element or an
gap at the desired index. index out of bounds error.

Deletion Overwrite the deleted element by Forgetting to decrease the

shifting all subsequent elements logical size counter of the array.
forward (j+1 to j).

Code snippet

// Assume 'myArray' is an array with a logical size 'currentSize'

// Pseudocode for Insertion at index 'idx' (0 <= idx <= currentSize)

PROCEDURE InsertElement(myArray, currentSize, element, idx)

 IF currentSize < MAX_SIZE THEN

// Start from the last element and shift backwards to make space

FOR i ← currentSize TO idx + 1 STEP -1 DO

myArray[i] ← myArray[i - 1]

END FOR

myArray[idx] ← element // Place the new element in the gap

currentSize ← currentSize + 1

ELSE

OUTPUT "Array is full."

END IF

END PROCEDURE

2. Sorting Algorithms
2.1 Topic Overview
Sorting algorithms rearrange elements in a list or array into a specific order (ascending or descending). They
are fundamental to data organization.

Algorithm Big-O Core Principle Exam Command

Type Efficiency Term

O(n²) $O(n^2)$ Repeated comparisons and Describe the

(Quadratic) swaps/placement of mechanism, trace
elements. Good for small steps.
data sets.

O(n log n) $O(n \log n)$ Divide and Conquer Explain the
(Log-Linear) strategy. Efficient for large recursive structure,
data sets. construct
pseudocode.

2.2 Iterative Sorting Algorithms (O(n²))

Bubble Sort (with Early Exit)
Principle: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the
wrong order. The largest element "bubbles" up to the end in each pass.
Code snippet

PROCEDURE BubbleSort(array)

n ← LENGTH(array)

FOR i ← 0 TO n - 2 DO // Outer loop controls the number of passes

swapped ← FALSE // Flag for Early Exit Optimization

// Inner loop performs comparisons/swaps. 'n - 1 - i' is the unsorted portion.

FOR j ← 0 TO n - i - 2 DO

IF array[j] > array[j + 1] THEN

// Swap array[j] and array[j + 1]

temp ← array[j]

array[j] ← array[j + 1]

array[j + 1] ← temp

swapped ← TRUE

END IF

END FOR

IF swapped = FALSE THEN

EXIT FOR // Early exit: No swaps occurred, list is sorted.

END IF

END FOR

END PROCEDURE

Conceptual Notes:
●​ Trace Table Tip: Only show the array after each pass of the outer loop, not after every single swap,
unless specified.
●​ Common Mistake: Incorrect loop range (n-1 vs n-2 vs n-i-1).
●​ Complexity:
○​ Worst/Average: $O(n^2)$
○​ Best (with early exit): $O(n)$

Selection Sort
Principle: Finds the minimum element in the unsorted portion and swaps it with the element at the beginning
of the unsorted portion.

Code snippet

PROCEDURE SelectionSort(array)

n ← LENGTH(array)

FOR i ← 0 TO n - 2 DO // i is the starting index of the unsorted section

minIndex ← i // Assume the current element is the smallest

// Find the smallest element in the remaining unsorted array

FOR j ← i + 1 TO n - 1 DO

IF array[j] < array[minIndex] THEN

minIndex ← j

END IF

END FOR

// Swap the found minimum element with the element at index i

// This places the correct element at position i

temp ← array[i]

array[i] ← array[minIndex]

array[minIndex] ← temp

END FOR

END PROCEDURE

Complexity: $O(n^2)$ for all cases (Best, Worst, Average) because it always performs $n(n-1)/2$
comparisons, regardless of initial order.

Insertion Sort
Principle: Builds the final sorted array one item at a time. It iterates, taking elements from the input data and
inserting them into the correct position in the already sorted part of the array.

Code snippet

PROCEDURE InsertionSort(array)
 n ← LENGTH(array)

FOR i ← 1 TO n - 1 DO // i starts at 1, assuming array[0] is the sorted section

currentValue ← array[i] // Element to be inserted

position ← i // Starting position for shifting

// Shift elements in the sorted portion (left of i) to the right

// until the correct position is found

WHILE position > 0 AND array[position - 1] > currentValue DO

array[position] ← array[position - 1] // Shift element right

position ← position - 1

END WHILE

array[position] ← currentValue // Insert the element

END FOR

END PROCEDURE

Complexity:
●​ Worst/Average: $O(n^2)$
●​ Best (nearly sorted): $O(n)$

2.3 Recursive Sorting Algorithms ($O(n \log n)$)

Both Merge Sort and Quick Sort use the Divide and Conquer paradigm.

Merge Sort (Divide and Conquer)

Principle:
1.​ Divide: Split the array into two halves until single-element arrays are reached.
2.​ Conquer/Merge: Repeatedly merge the sub-arrays to produce new sorted sub-arrays until one sorted
array remains.

Code snippet

// Merge Sort (The Recursive Splitter)

PROCEDURE MergeSort(array)

n ← LENGTH(array)
 IF n < 2 THEN

RETURN array // Base Case: An array of 0 or 1 element is sorted

END IF

mid ← FLOOR(n / 2)

// Divide step: Split array into left and right halves

leftHalf ← SUBARRAY(array, 0, mid - 1)

rightHalf ← SUBARRAY(array, mid, n - 1)

// Recursive step

leftHalf ← MergeSort(leftHalf)

rightHalf ← MergeSort(rightHalf)

// Conquer step: Combine the sorted halves

RETURN Merge(leftHalf, rightHalf)

END PROCEDURE

// Merge (The Combiner) - Simplistic outline of the merging logic

FUNCTION Merge(left, right) RETURNS ARRAY

result ← []

// Use pointers/indices to compare and append smallest from left/right to result

WHILE left IS NOT EMPTY AND right IS NOT EMPTY DO

IF left[0] < right[0] THEN

APPEND(result, REMOVE_FIRST(left))

ELSE

APPEND(result, REMOVE_FIRST(right))

END IF

END WHILE
 // Append remaining elements (one array will be empty)

APPEND_ALL(result, left)

APPEND_ALL(result, right)

RETURN result

END FUNCTION

Complexity: $O(n \log n)$ for all cases.

Quick Sort (Divide and Conquer)

Principle:
1.​ Partition: Select a pivot element and rearrange the array so that all elements less than the pivot are
before it, and all elements greater are after it.
2.​ Conquer: Recursively apply Quick Sort to the sub-arrays of elements less than and greater than the
pivot.

Code snippet

// Quick Sort (High-level recursive structure)

PROCEDURE QuickSort(array, low, high)

// Base Case: Sub-array size is 0 or 1 (low >= high)

IF low < high THEN

// Partition step: Selects a pivot and places it in its final sorted position

pivotIndex ← Partition(array, low, high)

// Recursive step: Sort the sub-arrays

QuickSort(array, low, pivotIndex - 1) // Sort left partition

QuickSort(array, pivotIndex + 1, high) // Sort right partition

END IF

END PROCEDURE

// Partition Function - (Implementation detail varies but ensures O(n) partitioning)

FUNCTION Partition(array, low, high) RETURNS INTEGER

// 1. Choose a pivot (e.g., array[high])

pivot ← array[high]
 // 2. Iterate from low to high-1, swapping elements < pivot to the left side

i ← low - 1

FOR j ← low TO high - 1 DO

IF array[j] <= pivot THEN

i←i+1

// Swap array[i] and array[j]

END IF

END FOR

// 3. Swap pivot (array[high]) with array[i + 1])

// This places the pivot in its final sorted position

RETURN i + 1 // Return the pivot's final index

END FUNCTION

Complexity:
●​ Worst (poor pivot choice): $O(n^2)$ (e.g., already sorted array using first/last element as pivot).
●​ Best/Average: $O(n \log n)$

3. Recursion
3.1 Topic Overview
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of
the same problem. A recursive function calls itself.

Concept Purpose Analogy Key Principle

Recursion Provides elegant, often Russian nesting dolls Base Case is

shorter, solutions to (Matryoshka) or essential to
problems with a mirrors facing each prevent infinite
self-similar structure. other. loop.
 Base Case The stopping condition; The smallest doll in
the smallest, the set.
non-recursive instance
of the problem that can
be solved directly.

Recursive The part where the Opening a larger doll

Case function calls itself with to find a smaller one.
a smaller input, working
towards the base case.

3.2 Common Recursive Algorithms

Factorial Calculation (n!)
Formula: n!=n×(n−1)!

Base Case: 0!=1

Code snippet

FUNCTION Factorial(n) RETURNS INTEGER

IF n = 0 THEN

RETURN 1 // Base Case: Stop the recursion

ELSE

// Recursive Case: Calls itself with a smaller input (n-1)

RETURN n * Factorial(n - 1)

END IF

END FUNCTION

Fibonacci Sequence
Formula: Fib(n)=Fib(n−1)+Fib(n−2)

Base Cases: Fib(0)=0, Fib(1)=1

Code snippet

FUNCTION Fibonacci(n) RETURNS INTEGER

IF n = 0 THEN

RETURN 0 // Base Case 1

ELSE IF n = 1 THEN

RETURN 1 // Base Case 2

 ELSE

// Recursive Case: Requires two previous calls

RETURN Fibonacci(n - 1) + Fibonacci(n - 2)

END IF

END FUNCTION

Conceptual Notes:
●​ Stack Behavior: Each recursive call pushes a new stack frame onto the Call Stack. The stack holds
the state (local variables, parameters) of the function call. When the base case is hit, the function
returns, and the stack frame is popped, allowing the function that called it to complete its calculation.
●​ Common Mistake: Omitting or incorrectly defining the base case, resulting in Stack Overflow Error
(infinite recursion).
●​ Recursive vs. Iterative: Recursion is often clearer but has higher overhead due to stack management.
Iteration is generally faster and uses less memory.

4. Abstract Data Types (ADTs): Stacks and Queues

4.1 Topic Overview
ADTs define a set of data and a set of operations, hiding the underlying implementation (e.g., using an Array
or a Linked List).

ADT Definition Analogy Primary Application

(Rule)

Stack LIFO (Last In, A stack of Tracking function calls (Call

First Out) cafeteria trays. Stack), Expression evaluation,
Undo/Redo mechanisms.

Queue FIFO (First In, A line of people at Task scheduling (printers, CPU),
First Out) a checkout Buffering data streams.
counter.

4.2 Stack Operations Pseudocode

A Stack typically uses a fixed-size array and a TopPointer variable.

Code snippet

// Assume STACK_ARRAY is the array, and TOP is the index of the top element.

// MAX_SIZE is the fixed size.

PROCEDURE PUSH(data, STACK_ARRAY, TOP)

// Checks for overflow (stack is full)

IF TOP = MAX_SIZE - 1 THEN

OUTPUT "Stack Overflow: Cannot push."

ELSE

TOP ← TOP + 1 // Increment pointer

STACK_ARRAY[TOP] ← data // Add item

END IF

END PROCEDURE

FUNCTION POP(STACK_ARRAY, TOP) RETURNS DATA_TYPE

// Checks for underflow (stack is empty)

IF TOP = -1 THEN

OUTPUT "Stack Underflow: Cannot pop."

RETURN NULL

ELSE

data ← STACK_ARRAY[TOP] // Retrieve item

TOP ← TOP - 1 // Decrement pointer

RETURN data

END IF

END FUNCTION

FUNCTION PEEK(STACK_ARRAY, TOP) RETURNS DATA_TYPE

// Looks at the top item without removing it

IF TOP > -1 THEN

RETURN STACK_ARRAY[TOP]

ELSE

RETURN NULL

END IF
END FUNCTION

FUNCTION IsEmpty(TOP) RETURNS BOOLEAN

RETURN TOP = -1

END FUNCTION

4.3 Queue Operations Pseudocode

A Queue typically uses a fixed-size array and two pointers: FrontPointer (for DEQUEUE) and RearPointer (for
ENQUEUE). A Circular Queue implementation is often preferred to manage fixed-size array space efficiently.

Code snippet

// Assume QUEUE_ARRAY, FRONT, REAR, and SIZE_LIMIT (max size)

PROCEDURE ENQUEUE(data, QUEUE_ARRAY, FRONT, REAR)

// Check for full queue (specific check depends on implementation, e.g., circular queue)

IF (REAR + 1) MOD SIZE_LIMIT = FRONT THEN

OUTPUT "Queue is full."

ELSE

REAR ← (REAR + 1) MOD SIZE_LIMIT // Update rear pointer (circular)

QUEUE_ARRAY[REAR] ← data

END IF

END PROCEDURE

FUNCTION DEQUEUE(QUEUE_ARRAY, FRONT, REAR) RETURNS DATA_TYPE

// Check for empty queue (e.g., FRONT = REAR for empty circular queue)

IF FRONT = REAR THEN

OUTPUT "Queue is empty."

RETURN NULL

ELSE

FRONT ← (FRONT + 1) MOD SIZE_LIMIT // Update front pointer

RETURN QUEUE_ARRAY[FRONT]

END IF
END FUNCTION

5. Algorithm Design & Dry Run

5.1 Flow of Control

Structure Pseudocode Keyword Purpose

Sequence (None) Statements are executed one after the

other.

Selection IF...THEN...ELSE...END IF Executes different code paths based

on a condition.

Iteration FOR...TO...DO...END FOR Fixed number of repetitions

(Count-controlled loop).

Iteration WHILE...DO...END WHILE Repeats as long as a condition is

TRUE (Condition-controlled loop).

Iteration REPEAT...UNTIL Repeats until a condition is TRUE

(post-test loop, runs at least once).

5.2 Parameter Passing

●​ Pass by Value: A copy of the actual parameter is passed to the procedure/function. Changes inside
the subprogram do not affect the original variable. Used for primitive data types (integers, booleans).
●​ Pass by Reference: The memory address (reference) of the actual parameter is passed. Changes
inside the subprogram do affect the original variable. Used for large data structures like arrays or
objects.

5.3 Trace Tables (Dry Run)

A trace table is used to manually execute an algorithm step-by-step to verify logic and predict output.

Step Line/Action Variable Variable Condition Output Notes

1 (e.g., i) 2 (e.g., (T/F)
sum)
 1 i←0 0 - - - Initialize
counter

2 WHILE i < 3 0 - T - Enter loop

3 sum ← sum 0 0 - - Execute

+i body

4 i←i+1 1 0 - - Increment
counter

5 WHILE i < 3 1 0 T - ...and so

on

📝 Exam-Focused Algorithm Cheat Sheet

Sorting Algorithm Comparison
Method Type Stability In-Plac Worst Case Best Case
e? Complexity Complexity

Bubble Comparison Stable Yes $O(n^2)$ $O(n)$ (w/

Early Exit)

Selection Comparison Not Yes $O(n^2)$ $O(n^2)$

Stable

Insertion Comparison Stable Yes $O(n^2)$ $O(n)$

Merge Comparison Stable No $O(n \log n)$ $O(n \log n)$

Quick Comparison Not Yes $O(n^2)$ $O(n \log n)$

Stable
 ●​ ​
Stability: A stable sort preserves the relative order of records with equal keys.
●​ In-Place: Requires only a constant amount of extra memory space.

Key Pseudocode Structures

Structure Template Note

Array FOR i ← 0 TO LENGTH(array) - 1 Standard loop, watch for

Traversal DO...END FOR off-by-one errors.

Sentinel WHILE input ≠ sentinel_value Condition-controlled; loop

Loop DO...END WHILE body must update the
input variable.

Function FUNCTION functionName(param1, Must include RETURNS

Definition param2) RETURNS DATA_TYPE and end with a RETURN
statement.

Recursion Structure Template

Code snippet

FUNCTION RecursiveFunction(input) RETURNS DATA_TYPE

// 1. Base Case: The stopping condition

IF base_condition IS TRUE THEN

RETURN base_value

ELSE

// 2. Recursive Case: Calls itself with a smaller input

result ← operation(RecursiveFunction(smaller_input))

RETURN result

END IF

END FUNCTION

Stack vs. Queue Quick Reference

 Feature Stack (LIFO) Queue (FIFO)

Insertion PUSH (Adds to the TOP) ENQUEUE (Adds to the

REAR)

Removal POP (Removes from the TOP) DEQUEUE (Removes from

the FRONT)

Check Top PEEK PEEK/FRONT

Applications Backtracking, Call Stacks, Scheduling, Buffering

Expression Evaluation

IB Command Term Tips for Algorithm Questions

Command Action Required Focus Area
Term

Describe Give a detailed account of how Explain the steps of the Bubble
something works. Sort in words.

Outline Give a brief account or List the steps of a Divide and

summary of the main features. Conquer approach.

Explain Give a detailed account of Justify why Binary Search is

reasons or mechanisms. $O(\log n)$.

Construct Create the required item (e.g., Write the pseudocode for
pseudocode, trace table). Insertion Sort.

Trace Show the execution of an Use a trace table to show how

algorithm step-by-step. Quick Sort partitions an array.

xity, and conceptual understanding.

🤖 IBDP Computer Science HL: Algorithm
Revision Guide
1. Data Structures: Arrays (Static)
1.1 Topic Overview
An Array is a linear, static data structure that stores a collection of elements of the same data type in
contiguous memory locations. Each element is accessed via an index.

Concept Purpose Analogy Complexity IB Command

Term Focus

Array Store multiple A set of O(1) for direct Outline the

related data labeled access structure,
items of the pigeonholes (indexing). explain index
same type under or mailboxes. addressing.
a single variable
name.

Traversal Systematically Reading O(n) Construct a

visit every every book on loop for
element once. a single shelf. traversal.

Multi-D Store tabular A O(1) for direct Explain

Array data or matrices. spreadsheet access indexing and
(rows and array[r][c]. storage
columns). (row/column-m
ajor).

1.2 Traversal and Searching Pseudocode

Linear Search
Used on unsorted or sorted arrays. It checks every element sequentially until the target is found.

Algorithm Big-O Complexity Optimization Note

Name

Linear Search Best: O(1) (First Early exit as soon as the element is
element) found.
 Worst/Average: O(n)

Code snippet

FUNCTION LinearSearch(data, target) RETURNS INTEGER

// data: The array to search, target: The value being sought
n ← LENGTH(data)

FOR i ← 0 TO n - 1 DO // Traverses the array from start to end

IF data[i] = target THEN
RETURN i // Found: Return the index immediately (Early Exit)
END IF
END FOR

RETURN -1 // Not found: Return a special value (e.g., -1)

END FUNCTION

Binary Search
Requires the array to be sorted. It repeatedly halves the search interval.

Algorithm Big-O Complexity Optimization Note

Name

Binary Search Best: O(1) Requires the array to be sorted first

(O(n log n) cost).

Worst/Average: O(log
n)

Code snippet

FUNCTION BinarySearch(data, target) RETURNS INTEGER

// data MUST be sorted
low ← 0 // Index of the first element
high ← LENGTH(data) - 1 // Index of the last element

WHILE low <= high DO // Continue searching while a valid range exists
mid ← FLOOR((low + high) / 2) // Calculate the middle index (integer division)

IF data[mid] = target THEN

RETURN mid // Found the target
ELSE IF data[mid] < target THEN
low ← mid + 1 // Target must be in the upper half
ELSE
high ← mid - 1 // Target must be in the lower half
END IF
END WHILE
 RETURN -1 // Not found
END FUNCTION

1.3 Insertion and Deletion Logic

Insertion and deletion in a static array typically involve shifting other elements, making them O(n) operations.

Operation Logic Common Mistake

Insertion Start at the last element and shift Incorrect loop range, leading to
backwards (j to j-1) to create a overwriting the last element or an
gap at the desired index. index out of bounds error.

Deletion Overwrite the deleted element by Forgetting to decrease the

shifting all subsequent elements logical size counter of the array.
forward (j+1 to j).

Code snippet

// Assume 'myArray' is an array with a logical size 'currentSize'

// Pseudocode for Insertion at index 'idx' (0 <= idx <= currentSize)
PROCEDURE InsertElement(myArray, currentSize, element, idx)
IF currentSize < MAX_SIZE THEN
// Start from the last element and shift backwards to make space
FOR i ← currentSize TO idx + 1 STEP -1 DO
myArray[i] ← myArray[i - 1]
END FOR
myArray[idx] ← element // Place the new element in the gap
currentSize ← currentSize + 1
ELSE
OUTPUT "Array is full."
END IF
END PROCEDURE

2. Sorting Algorithms
2.1 Topic Overview
Sorting algorithms rearrange elements in a list or array into a specific order (ascending or descending). They
are fundamental to data organization.

Algorithm Big-O Core Principle Exam Command

Type Efficiency Term
 O(n²) $O(n^2)$ Repeated comparisons and Describe the
(Quadratic) swaps/placement of mechanism, trace
elements. Good for small steps.
data sets.

O(n log n) $O(n \log n)$ Divide and Conquer Explain the
(Log-Linear) strategy. Efficient for large recursive structure,
data sets. construct
pseudocode.

2.2 Iterative Sorting Algorithms (O(n²))

Bubble Sort (with Early Exit)
Principle: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the
wrong order. The largest element "bubbles" up to the end in each pass.

Code snippet

PROCEDURE BubbleSort(array)
n ← LENGTH(array)

FOR i ← 0 TO n - 2 DO // Outer loop controls the number of passes

swapped ← FALSE // Flag for Early Exit Optimization

// Inner loop performs comparisons/swaps. 'n - 1 - i' is the unsorted portion.

FOR j ← 0 TO n - i - 2 DO
IF array[j] > array[j + 1] THEN
// Swap array[j] and array[j + 1]
temp ← array[j]
array[j] ← array[j + 1]
array[j + 1] ← temp
swapped ← TRUE
END IF
END FOR

IF swapped = FALSE THEN

EXIT FOR // Early exit: No swaps occurred, list is sorted.
END IF
END FOR
END PROCEDURE

Conceptual Notes:
●​ Trace Table Tip: Only show the array after each pass of the outer loop, not after every single swap,
unless specified.
●​ Common Mistake: Incorrect loop range (n-1 vs n-2 vs n-i-1).
●​ Complexity:
○​ Worst/Average: $O(n^2)$
○​ Best (with early exit): $O(n)$
Selection Sort
Principle: Finds the minimum element in the unsorted portion and swaps it with the element at the beginning
of the unsorted portion.

Code snippet

PROCEDURE SelectionSort(array)
n ← LENGTH(array)

FOR i ← 0 TO n - 2 DO // i is the starting index of the unsorted section

minIndex ← i // Assume the current element is the smallest

// Find the smallest element in the remaining unsorted array

FOR j ← i + 1 TO n - 1 DO
IF array[j] < array[minIndex] THEN
minIndex ← j
END IF
END FOR

// Swap the found minimum element with the element at index i

// This places the correct element at position i
temp ← array[i]
array[i] ← array[minIndex]
array[minIndex] ← temp

END FOR
END PROCEDURE

Complexity: $O(n^2)$ for all cases (Best, Worst, Average) because it always performs $n(n-1)/2$
comparisons, regardless of initial order.

Insertion Sort
Principle: Builds the final sorted array one item at a time. It iterates, taking elements from the input data and
inserting them into the correct position in the already sorted part of the array.

Code snippet

PROCEDURE InsertionSort(array)
n ← LENGTH(array)

FOR i ← 1 TO n - 1 DO // i starts at 1, assuming array[0] is the sorted section

currentValue ← array[i] // Element to be inserted
position ← i // Starting position for shifting

// Shift elements in the sorted portion (left of i) to the right

// until the correct position is found
WHILE position > 0 AND array[position - 1] > currentValue DO
array[position] ← array[position - 1] // Shift element right
position ← position - 1
END WHILE

array[position] ← currentValue // Insert the element

END FOR
END PROCEDURE
Complexity:
●​ Worst/Average: $O(n^2)$
●​ Best (nearly sorted): $O(n)$

2.3 Recursive Sorting Algorithms ($O(n \log n)$)

Both Merge Sort and Quick Sort use the Divide and Conquer paradigm.

Merge Sort (Divide and Conquer)

Principle:
1.​ Divide: Split the array into two halves until single-element arrays are reached.
2.​ Conquer/Merge: Repeatedly merge the sub-arrays to produce new sorted sub-arrays until one sorted
array remains.

Code snippet

// Merge Sort (The Recursive Splitter)

PROCEDURE MergeSort(array)
n ← LENGTH(array)

IF n < 2 THEN
RETURN array // Base Case: An array of 0 or 1 element is sorted
END IF

mid ← FLOOR(n / 2)

// Divide step: Split array into left and right halves

leftHalf ← SUBARRAY(array, 0, mid - 1)
rightHalf ← SUBARRAY(array, mid, n - 1)

// Recursive step
leftHalf ← MergeSort(leftHalf)
rightHalf ← MergeSort(rightHalf)

// Conquer step: Combine the sorted halves

RETURN Merge(leftHalf, rightHalf)
END PROCEDURE

// Merge (The Combiner) - Simplistic outline of the merging logic

FUNCTION Merge(left, right) RETURNS ARRAY
result ← []
// Use pointers/indices to compare and append smallest from left/right to result
WHILE left IS NOT EMPTY AND right IS NOT EMPTY DO
IF left[0] < right[0] THEN
APPEND(result, REMOVE_FIRST(left))
ELSE
APPEND(result, REMOVE_FIRST(right))
END IF
END WHILE

// Append remaining elements (one array will be empty)

APPEND_ALL(result, left)
 APPEND_ALL(result, right)

RETURN result
END FUNCTION

Complexity: $O(n \log n)$ for all cases.

Quick Sort (Divide and Conquer)

Principle:
1.​ Partition: Select a pivot element and rearrange the array so that all elements less than the pivot are
before it, and all elements greater are after it.
2.​ Conquer: Recursively apply Quick Sort to the sub-arrays of elements less than and greater than the
pivot.

Code snippet

// Quick Sort (High-level recursive structure)

PROCEDURE QuickSort(array, low, high)
// Base Case: Sub-array size is 0 or 1 (low >= high)
IF low < high THEN
// Partition step: Selects a pivot and places it in its final sorted position
pivotIndex ← Partition(array, low, high)

// Recursive step: Sort the sub-arrays

QuickSort(array, low, pivotIndex - 1) // Sort left partition
QuickSort(array, pivotIndex + 1, high) // Sort right partition
END IF
END PROCEDURE

// Partition Function - (Implementation detail varies but ensures O(n) partitioning)

FUNCTION Partition(array, low, high) RETURNS INTEGER
// 1. Choose a pivot (e.g., array[high])
pivot ← array[high]

// 2. Iterate from low to high-1, swapping elements < pivot to the left side
i ← low - 1
FOR j ← low TO high - 1 DO
IF array[j] <= pivot THEN
i←i+1
// Swap array[i] and array[j]
END IF
END FOR

// 3. Swap pivot (array[high]) with array[i + 1])

// This places the pivot in its final sorted position

RETURN i + 1 // Return the pivot's final index

END FUNCTION

Complexity:
●​ Worst (poor pivot choice): $O(n^2)$ (e.g., already sorted array using first/last element as pivot).
●​ Best/Average: $O(n \log n)$
3. Recursion
3.1 Topic Overview
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of
the same problem. A recursive function calls itself.

Concept Purpose Analogy Key Principle

Recursion Provides elegant, often Russian nesting dolls Base Case is

shorter, solutions to (Matryoshka) or essential to
problems with a mirrors facing each prevent infinite
self-similar structure. other. loop.

Base Case The stopping condition; The smallest doll in

the smallest, the set.
non-recursive instance
of the problem that can
be solved directly.

Recursive The part where the Opening a larger doll

Case function calls itself with to find a smaller one.
a smaller input, working
towards the base case.

3.2 Common Recursive Algorithms

Factorial Calculation (n!)
Formula: n!=n×(n−1)!

Base Case: 0!=1

Code snippet

FUNCTION Factorial(n) RETURNS INTEGER

IF n = 0 THEN
RETURN 1 // Base Case: Stop the recursion
ELSE
// Recursive Case: Calls itself with a smaller input (n-1)
RETURN n * Factorial(n - 1)
END IF
END FUNCTION

Fibonacci Sequence
Formula: Fib(n)=Fib(n−1)+Fib(n−2)
Base Cases: Fib(0)=0, Fib(1)=1

Code snippet

FUNCTION Fibonacci(n) RETURNS INTEGER

IF n = 0 THEN
RETURN 0 // Base Case 1
ELSE IF n = 1 THEN
RETURN 1 // Base Case 2
ELSE
// Recursive Case: Requires two previous calls
RETURN Fibonacci(n - 1) + Fibonacci(n - 2)
END IF
END FUNCTION

Conceptual Notes:
●​ Stack Behavior: Each recursive call pushes a new stack frame onto the Call Stack. The stack holds
the state (local variables, parameters) of the function call. When the base case is hit, the function
returns, and the stack frame is popped, allowing the function that called it to complete its calculation.
●​ Common Mistake: Omitting or incorrectly defining the base case, resulting in Stack Overflow Error
(infinite recursion).
●​ Recursive vs. Iterative: Recursion is often clearer but has higher overhead due to stack management.
Iteration is generally faster and uses less memory.

4. Abstract Data Types (ADTs): Stacks and Queues

4.1 Topic Overview
ADTs define a set of data and a set of operations, hiding the underlying implementation (e.g., using an Array
or a Linked List).

ADT Definition Analogy Primary Application

(Rule)

Stack LIFO (Last In, A stack of Tracking function calls (Call

First Out) cafeteria trays. Stack), Expression evaluation,
Undo/Redo mechanisms.

Queue FIFO (First In, A line of people at Task scheduling (printers, CPU),
First Out) a checkout Buffering data streams.
counter.

4.2 Stack Operations Pseudocode

A Stack typically uses a fixed-size array and a TopPointer variable.

Code snippet
// Assume STACK_ARRAY is the array, and TOP is the index of the top element.
// MAX_SIZE is the fixed size.

PROCEDURE PUSH(data, STACK_ARRAY, TOP)

// Checks for overflow (stack is full)
IF TOP = MAX_SIZE - 1 THEN
OUTPUT "Stack Overflow: Cannot push."
ELSE
TOP ← TOP + 1 // Increment pointer
STACK_ARRAY[TOP] ← data // Add item
END IF
END PROCEDURE

FUNCTION POP(STACK_ARRAY, TOP) RETURNS DATA_TYPE

// Checks for underflow (stack is empty)
IF TOP = -1 THEN
OUTPUT "Stack Underflow: Cannot pop."
RETURN NULL
ELSE
data ← STACK_ARRAY[TOP] // Retrieve item
TOP ← TOP - 1 // Decrement pointer
RETURN data
END IF
END FUNCTION

FUNCTION PEEK(STACK_ARRAY, TOP) RETURNS DATA_TYPE

// Looks at the top item without removing it
IF TOP > -1 THEN
RETURN STACK_ARRAY[TOP]
ELSE
RETURN NULL
END IF
END FUNCTION

FUNCTION IsEmpty(TOP) RETURNS BOOLEAN

RETURN TOP = -1
END FUNCTION

4.3 Queue Operations Pseudocode

A Queue typically uses a fixed-size array and two pointers: FrontPointer (for DEQUEUE) and RearPointer (for
ENQUEUE). A Circular Queue implementation is often preferred to manage fixed-size array space efficiently.

Code snippet

// Assume QUEUE_ARRAY, FRONT, REAR, and SIZE_LIMIT (max size)

PROCEDURE ENQUEUE(data, QUEUE_ARRAY, FRONT, REAR)

// Check for full queue (specific check depends on implementation, e.g., circular queue)
IF (REAR + 1) MOD SIZE_LIMIT = FRONT THEN
OUTPUT "Queue is full."
ELSE
REAR ← (REAR + 1) MOD SIZE_LIMIT // Update rear pointer (circular)
QUEUE_ARRAY[REAR] ← data
END IF
END PROCEDURE
FUNCTION DEQUEUE(QUEUE_ARRAY, FRONT, REAR) RETURNS DATA_TYPE
// Check for empty queue (e.g., FRONT = REAR for empty circular queue)
IF FRONT = REAR THEN
OUTPUT "Queue is empty."
RETURN NULL
ELSE
FRONT ← (FRONT + 1) MOD SIZE_LIMIT // Update front pointer
RETURN QUEUE_ARRAY[FRONT]
END IF
END FUNCTION

5. Algorithm Design & Dry Run

5.1 Flow of Control

Structure Pseudocode Keyword Purpose

Sequence (None) Statements are executed one after the

other.

Selection IF...THEN...ELSE...END IF Executes different code paths based

on a condition.

Iteration FOR...TO...DO...END FOR Fixed number of repetitions

(Count-controlled loop).

Iteration WHILE...DO...END WHILE Repeats as long as a condition is

TRUE (Condition-controlled loop).

Iteration REPEAT...UNTIL Repeats until a condition is TRUE

(post-test loop, runs at least once).

5.2 Parameter Passing

●​ Pass by Value: A copy of the actual parameter is passed to the procedure/function. Changes inside
the subprogram do not affect the original variable. Used for primitive data types (integers, booleans).
●​ Pass by Reference: The memory address (reference) of the actual parameter is passed. Changes
inside the subprogram do affect the original variable. Used for large data structures like arrays or
objects.

5.3 Trace Tables (Dry Run)

A trace table is used to manually execute an algorithm step-by-step to verify logic and predict output.

Step Line/Action Variable Variable Condition Output Notes

1 (e.g., i) 2 (e.g., (T/F)
sum)

1 i←0 0 - - - Initialize
counter

2 WHILE i < 3 0 - T - Enter loop

3 sum ← sum 0 0 - - Execute

+i body

4 i←i+1 1 0 - - Increment
counter

5 WHILE i < 3 1 0 T - ...and so

on

📝 Exam-Focused Algorithm Cheat Sheet

Sorting Algorithm Comparison
Method Type Stability In-Plac Worst Case Best Case
e? Complexity Complexity

Bubble Comparison Stable Yes $O(n^2)$ $O(n)$ (w/

Early Exit)

Selection Comparison Not Yes $O(n^2)$ $O(n^2)$

Stable

Insertion Comparison Stable Yes $O(n^2)$ $O(n)$

 Merge Comparison Stable No $O(n \log n)$ $O(n \log n)$

Quick Comparison Not Yes $O(n^2)$ $O(n \log n)$

Stable

●​ ​
Stability: A stable sort preserves the relative order of records with equal keys.
●​ In-Place: Requires only a constant amount of extra memory space.

Key Pseudocode Structures

Structure Template Note

Array FOR i ← 0 TO LENGTH(array) - 1 Standard loop, watch for

Traversal DO...END FOR off-by-one errors.

Sentinel WHILE input ≠ sentinel_value Condition-controlled; loop

Loop DO...END WHILE body must update the
input variable.

Function FUNCTION functionName(param1, Must include RETURNS

Definition param2) RETURNS DATA_TYPE and end with a RETURN
statement.

Recursion Structure Template

Code snippet

FUNCTION RecursiveFunction(input) RETURNS DATA_TYPE

// 1. Base Case: The stopping condition
IF base_condition IS TRUE THEN
RETURN base_value
ELSE
// 2. Recursive Case: Calls itself with a smaller input
result ← operation(RecursiveFunction(smaller_input))
RETURN result
END IF
END FUNCTION

Stack vs. Queue Quick Reference

 Feature Stack (LIFO) Queue (FIFO)

Insertion PUSH (Adds to the TOP) ENQUEUE (Adds to the

REAR)

Removal POP (Removes from the TOP) DEQUEUE (Removes from

the FRONT)

Check Top PEEK PEEK/FRONT

Applications Backtracking, Call Stacks, Scheduling, Buffering

Expression Evaluation

IB Command Term Tips for Algorithm Questions

Command Action Required Focus Area
Term

Describe Give a detailed account of how Explain the steps of the Bubble
something works. Sort in words.

Outline Give a brief account or List the steps of a Divide and

summary of the main features. Conquer approach.

Explain Give a detailed account of Justify why Binary Search is

reasons or mechanisms. $O(\log n)$.

Construct Create the required item (e.g., Write the pseudocode for
pseudocode, trace table). Insertion Sort.

Trace Show the execution of an Use a trace table to show how

algorithm step-by-step. Quick Sort partitions an array.

​
​
​
The PDF you provided, "Topic 4: Computational Thinking & Problem Solving," is an excellent resource
that covers the standard algorithms on linear arrays and collections required by the IB Computer Science
1111111111111111
syllabus .
Here is a summary of the key algorithms and related concepts, including pseudocode examples, directly
extracted from your document:

💾 Standard Algorithms on Linear Arrays

2
The algorithms below operate on linear arrays (lists of elements in a continuous block of memory) .

1. Searching Algorithms
A. Sequential Search (Linear Search)
3
This method checks every element in the list, one at a time, in sequence, until the desired value is found .

Efficiency Case Complexity (Time) Note

Best Case $O(1)$ 4

Element is found at the first position .

Worst Case $O(n)$ Element is found at the end or is not in the

5
array .

Average Case $O(n)$ 6

Length of array/2 .

7
Sequential Search Pseudocode

Code snippet

INPUT target
SET found TO false

FOR i FROM 0 TO length - 1 LOOP

IF array[i] = target_value THEN
DISPLAY “Found at position”, i
SET found TO true
END IF
END LOOP

IF found = false THEN

DISPLAY “Not found”
END IF
B. Binary Search
This algorithm finds the position of a value within an array that must be sorted by comparing the search key
8 9
with the middle element . It then repeats the process on the sub-array to the left or right .

Requirement Complexity (Worst/Average)

10 $O(\log n)$
Array must be sorted

11
Binary Search Pseudocode

Code snippet

INPUT search_value
SET low TO 0
SET high TO length - 1

WHILE low <= high LOOP

SET mid TO (low + high) DIV 2

IF array[mid] = search_value THEN

DISPLAY "Found at", mid
EXIT LOOP
ELSE IF search_value < array[mid] THEN
SET high TO mid - 1
ELSE
SET low TO mid + 1
END IF
END LOOP

IF low > high THEN

DISPLAY "Not found"
END IF

2. Sorting Algorithms
All sorting algorithms below are comparison sorts and are often measured by their time
121212121212121212
efficiency .

A. Bubble Sort
This simple sorting algorithm repeatedly steps through the list, comparing adjacent items and swapping them
13131313
if they are in the wrong order . The process repeats until no swaps are needed, indicating the list is
14 15
sorted . Smaller elements "bubble" to the top .

16
Bubble Sort Pseudocode
Code snippet

FOR i FROM 0 TO length - 2 LOOP

// Outer loop controls number of passes
FOR j FROM 0 TO length - 2 - i LOOP
// Inner loop compares adjacent elements
IF array[j] > array[j + 1] THEN
SWAP array[j] WITH array[j + 1]
END IF
END LOOP
END LOOP

B. Selection Sort
17
This algorithm divides the list into sorted and unsorted portions . It works by finding the smallest element in
18181818
the unsorted sublist and swapping it with the leftmost unsorted element .

19
Selection Sort Pseudocode

Code snippet

FOR i FROM 0 TO length - 2 LOOP

SET min_index TO i

FOR j FROM i + 1 TO length - 1 LOOP

// Find the index of the minimum element in the unsorted sub-list
IF array[j] < array[min_index] THEN
SET min_index TO j
END IF
END LOOP

// Swap the minimum element with the current starting position (i)
IF min_index ≠ i THEN
SWAP array[i] WITH array[min_index]
END IF
END LOOP

📊 Algorithm Efficiency (Big O Notation)

The efficiency of an algorithm is measured by how well it performs in terms of Time (execution duration) and
20
Space (memory usage) .

21
●​ Time Complexity: Measures the time an algorithm takes as a function of the input size ($n$) .
22
●​ The common notation used to describe this is Big O notation .

🧺 Collections (Abstract Data Types)

 23
The IB syllabus defines collections as unordered lists, usually of unknown or dynamic size . These are
conceptual ADTs with a specific set of allowed operations:

Command Simple Meaning Description

addItem(item) Puts something in the 24

Adds a data item to the collection .
collection

resetNext() Goes back to the start Start at the beginning of the collection
252525
for traversal .

hasNext() Checks if there’s more to Tells whether there is another item in

take out 26
the list .

getNext() Takes out the next thing Retrieves a data item from the
27
collection .

isEmpty() Checks if the collection Checks whether the collection

is empty 282828
contains any items .

Note: You must be careful to only use these specified methods for collections, and avoid others like .size() or
29
.length() .

​
​
​
​
This revision guide covers IBDP Computer Science HL Topic 2: System Fundamentals, structured similarly

🖥️ IBDP Computer Science HL: System

to the algorithms guide, focusing on core concepts, definitions, and functions.

Fundamentals
1. Core Concepts: Systems, Components, and Interaction
1.1 Topic Overview
A system is a set of interacting or interdependent components forming an integrated whole. Computer
systems are defined by the interaction between hardware and software.
 Concept Definition & Analogy IB Command
Purpose Term Focus

System An organized A car (engine, Define system,

collection of parts wheels, steering describe
that work together to work together to components.
achieve a specific move).
function.

Interconnection The way components Roads and Explain the role

are connected (e.g., highways of buses (data,
buses, cables, connecting address, control).
network links). different cities.

Interface A point where two A light switch Distinguish

systems or (interface between user and
components meet between user hardware
and interact (e.g., and electrical interfaces.
GUI, API, hardware system).
ports).

1.2 System Inputs, Outputs, Processing, and Storage

All computer systems follow the basic Input-Process-Output-Storage model.

Element Role Examples

Input Data entering the system. Keyboard, mouse,

microphone, sensor data.

Processing Manipulation of data by the CPU to Executing instructions,

produce information. calculating, sorting data.

Output Information leaving the system. Monitor, speaker, printer,

network transmission.

Storage Holding data/information RAM (temporary), Hard Drive

persistently or temporarily. (persistent), Cache.
2. Hardware: The Von Neumann Architecture
Modern computers are based on the Von Neumann Architecture

Image of Von Neumann Architecture Diagram

, where data and instructions are stored in the same memory unit and accessed via a single bus.

2.1 Central Processing Unit (CPU)

The "brain" of the computer, responsible for executing instructions.

Component Function Detail

Arithmetic Logic Performs arithmetic (add, The calculator part of the CPU.
Unit (ALU) subtract) and logical
operations (AND, OR,
NOT).

Control Unit Directs and coordinates all Fetches instructions, decodes

(CU) operations within the CPU them, and executes them by
and the system. controlling the flow of data.

Registers Small, fast, temporary Store the address of the next

storage locations within the instruction (PC), instruction being
CPU. executed (IR), and temporary
data values.

2.2 The Fetch-Decode-Execute Cycle (FDE Cycle)

The fundamental process by which the CPU executes program instructions.

Phase CU Action Key Register(s) Involved

Fetch CU fetches the instruction stored at the PC, IR, Memory Address
memory address specified by the Register (MAR), Memory
Program Counter (PC) and moves it to Data Register (MDR).
the Instruction Register (IR).

Decode CU interprets the instruction in the IR to Instruction Register (IR).

determine the operation to be performed
and the operands (data).
 Execute CU issues control signals to the ALU and ALU, Accumulator (ACC),
other components to perform the other registers.
operation. Results are often stored in the
Accumulator (ACC) or memory.

3. Memory Hierarchy and Storage

Computer storage is organized in a hierarchy based on speed, capacity, and cost.

3.1 Memory Types

Type Volatility Access Primary Use

Speed

Registers Volatile Fastest Store data currently being processed

by the CPU.

Cache Volatile Very Fast Store frequently used data/instructions

Memory from RAM. L1 (fastest, smallest,
closest to CPU) $\rightarrow$ L2
$\rightarrow$ L3.

RAM Volatile Fast Main working memory for running

(Primary) programs and data.

ROM Non-Volatil Slow Stores the BIOS/UEFI (start-up

(Primary) e instructions). Read-only.

Secondary Non-Volatil Slowest Permanent storage (HDD, SSD, optical

Storage e discs).

Volatile: Requires power to maintain stored data.

Non-Volatile: Retains data even when power is turned off.

3.2 Storage Media Characteristics

Medium Mechanism Key Characteristic

 Hard Disk Drive Magnetic platters that spin; High capacity, low cost per GB,
(HDD) uses a read/write head. slowest access time (due to
physical movement).

Solid State Drive Flash memory Fastest access time, silent,

(SSD) (semiconductors). more durable, higher cost per
GB.

Optical Lasers read reflective Portable, low capacity,

(CD/DVD/Blu-ray) surfaces. sequential access.

4. Software: Operating Systems (OS)

The Operating System (OS) is system software that manages computer hardware and software resources
and provides common services for computer programs.

4.1 Key Functions of an OS

Function Description Example

Memory Allocates and deallocates Uses Paging or

Management memory space to running Segmentation to handle
programs. virtual memory.

Processor Schedules processes for CPU Time-slicing in a multi-tasking

Management execution (Scheduling). OS.

I/O Management Manages communication Device Drivers translate OS

between the computer and requests into hardware
input/output devices. commands.

File Organizes and controls access Uses a file system (e.g.,

Management to files on secondary storage. NTFS, FAT) to manage
folders and permissions.

User Interface Provides a means for users to GUI (Graphical User

interact with the system. Interface) or CLI (Command
Line Interface).
4.2 Multi-tasking vs. Multi-user
●​ Multi-tasking: Allows a single user to run multiple programs concurrently (e.g., listening to music
while typing a document). The OS switches the CPU between tasks rapidly (Time-Slicing).
●​ Multi-user: Allows multiple users to use the same computer system simultaneously (e.g., a server
accessed by many clients). The OS must manage resource allocation and isolation between user
sessions.

5. Software Layers and Types

Software Type Purpose Examples

System Designed to operate the computer Operating systems,

Software hardware and provide a platform for device drivers, utilities.
application software.

Application Designed to perform specific Web browsers, word

Software user-oriented tasks. processors, games.

5.1 Compilers vs. Interpreters

These are tools that convert high-level programming code into machine code the CPU can execute.

Feature Compiler Interpreter

Translation Translates the entire source Translates and executes the

code at once before source code line by line.
execution.

Speed Slow compilation, but fast No compilation step, but slow

execution. execution.

Error Reports all errors after the Stops execution immediately upon
Handling full compilation process. encountering an error.

Use Case Distribution of proprietary Scripting, rapid development, web

desktop applications (C, C++, environments (Python, JavaScript,
Java). PHP).

💡 Exam-Focused Cheat Sheet: System Fundamentals

 Concept Key Definition Related Term

CPU Executes FDE cycle using CU, Clock Speed (Hz) determines
ALU, and Registers. how fast the FDE cycle repeats.

Cache Fastest memory; stores frequently Locality of Reference (principle

accessed instructions/data from for cache effectiveness).
RAM.

RAM Volatile working memory for active Virtual Memory (uses

programs and data. secondary storage as an
extension of RAM).

ROM Non-volatile memory storing Bootstrapping (process of

start-up instructions (BIOS/UEFI). loading the OS from ROM).

OS System software that manages Scheduler (part of the OS that

hardware resources. manages CPU time for
processes).

Device Software that allows the OS to I/O Management (an OS

Driver communicate with a specific I/O function).
device.

You asked for a more detailed revision guide on IBDP Computer Science HL Topic 2: System
Fundamentals.

Here is an expanded guide, going into greater depth on the Von Neumann Architecture, memory
management, and software execution, suitable for Paper 1 and Paper 2 analysis questions.

💻 IBDP Computer Science HL: System

Fundamentals (Detailed)
1. Computer Architecture: The Von Neumann Model
The Von Neumann Architecture is the bedrock of most modern computing systems. It mandates that data
and instructions are stored in a single, shared memory space and that a single set of buses is used to
transfer both.
1.1 The Central Processing Unit (CPU)
The CPU is the hardware that executes instructions. Its performance is measured by Clock Speed (cycles per
second, in GHz) and Core Count.

Key CPU Components and Registers

Component Detailed Function

Arithmetic Logic Unit Executes all arithmetic operations (addition, subtraction,

(ALU) multiplication, division) and logical comparisons (AND,
OR, NOT). It processes data retrieved from registers.

Control Unit (CU) Coordinates and times all operations. It interprets

instructions from the Instruction Register (IR) and
generates the necessary control signals to components
(like the ALU, registers, and buses) to execute the
instruction.

Registers Fast, small memory blocks within the CPU used to

temporarily hold data, addresses, and instructions during
the FDE cycle.

Program Counter (PC) Stores the address of the next instruction to be

executed. It is incremented after the instruction address
is transferred to the MAR.

Instruction Register (IR) Stores the instruction currently being decoded and
executed.

Memory Address Stores the memory address from which data/instruction

Register (MAR) will be fetched, or to which data will be written.

Memory Data Register Stores the data or instruction that has just been fetched
(MDR) / Memory Buffer from memory or is about to be written to memory.
Register (MBR)

Accumulator (ACC) Stores the intermediate results of calculations performed

by the ALU.

1.2 The Fetch-Decode-Execute Cycle (FDE Cycle)

This is the fundamental, cyclic process the CPU uses to run programs.
1.​ FETCH:
○​ The address in the PC is copied to the MAR.
○​ The value in the PC is incremented to point to the next instruction.
○​ The instruction at the address in the MAR is copied from memory to the MDR.
○​ The instruction in the MDR is copied to the IR.
2.​ DECODE:
○​ The CU interprets the instruction in the IR, determining what operation is required and what
operands (data) are needed.
3.​ EXECUTE:
○​ The CU sends control signals to the necessary components (ALU, registers, memory) to carry
out the operation.
○​ If a calculation is needed, the ALU performs it, and the result is stored in the ACC.
○​ If a jump/branch instruction occurs, the PC is updated with a new memory address, altering the
flow of execution.

2. Memory Hierarchy and Data Locality

The memory hierarchy is designed to provide the fastest average access time while managing cost.

2.1 Cache Memory and Locality

Cache memory is the fastest volatile memory, operating at speeds close to the CPU. Its efficiency relies on
two principles:
●​ Temporal Locality: If a memory location is referenced, it is likely to be referenced again soon.
●​ Spatial Locality: If a memory location is referenced, memory locations nearby (spatially close) are
likely to be referenced soon.

The CPU checks the cache first (L1 $\rightarrow$ L2 $\rightarrow$ L3). A cache hit occurs when the data is
found in the cache; a cache miss requires fetching data from the next level (RAM).

2.2 RAM and Virtual Memory

Random Access Memory (RAM) is the main working memory. It is fast and volatile.
●​ Virtual Memory (VM): The OS uses VM when RAM is full. It swaps inactive sections of programs and
data (called pages or segments) between RAM and secondary storage (often a hard disk, called a
swap file or paging file).
○​ Advantage: Allows the system to run more programs than physically fit in RAM.
○​ Disadvantage: Accessing data from the swap file is extremely slow compared to RAM (known
as thrashing if excessive swapping occurs).

3. Operating System (OS) Management

The OS is the resource manager, ensuring efficient use of hardware.

3.1 Memory Management Techniques

The OS manages the physical and virtual address space of the system.
 ●​ Paging: Memory is divided into fixed-size blocks called pages. Programs are divided into pages.
When a process runs, its pages are loaded into any available frames (fixed-size blocks) of physical
memory.
○​ Advantage: Simple to manage; eliminates external fragmentation.
●​ Segmentation: Memory is divided into variable-size logical blocks called segments. Each segment
corresponds to a logical unit of a program (e.g., code, data stack).
○​ Advantage: Easier to implement memory protection and sharing based on logical units.

3.2 Process Management and Scheduling

The OS manages processes (running instances of programs) and uses a scheduler to decide which process
gets the CPU next. This is essential for multi-tasking.
●​ Time Slicing: Each process is allocated a small time interval (quantum) on the CPU. If the process is
not finished when the quantum expires, it is suspended, and the CPU moves to the next process. This
gives the illusion of simultaneous execution.
●​ Process States: A process cycles through states: New $\rightarrow$ Ready $\rightarrow$ Running
$\rightarrow$ Waiting $\rightarrow$ Terminated. The scheduler only deals with the Ready and
Running states.

3.3 I/O and Device Drivers

The OS handles communication with external devices.
●​ Interrupts: These are signals sent by hardware or software to the CPU to indicate that an event has
occurred and requires immediate attention (e.g., a key press, a disk transfer completion). The OS uses
an Interrupt Handler to service the request.
●​ Device Drivers: These are special software modules that act as translators. They provide a
standardized interface for the OS to communicate with specific hardware devices. The OS issues a
generic command; the driver translates it into the specific, low-level commands the hardware
understands.

4. Software Execution: Compilers vs. Interpreters

These tools represent different trade-offs between speed, portability, and error checking.

4.1 Compiler
A compiler translates the entire high-level source code into a single executable machine code file before the
program is run.
●​ Error Reporting: All errors are reported at once at the end of compilation.
●​ Execution: Execution is extremely fast because the CPU runs native machine code directly.
●​ Portability: The resulting machine code is specific to one CPU architecture (e.g., x86), requiring a
separate version for other platforms.

4.2 Interpreter
An interpreter translates and executes high-level source code instructions one line at a time as the program
runs.
Image of Interpreter process

●​ Error Reporting: Execution stops immediately upon encountering an error in the line being processed.
 ●​ Execution: Execution is slower because the interpretation process must happen repeatedly every
time the code runs.
●​ Portability: Source code can be run on any platform that has the correct interpreter installed, making
the source code highly portable.

4.3 Virtual Machine (VM)

Some languages (like Java) use a hybrid approach, compiling source code into bytecode, which is then
interpreted/executed by a Virtual Machine (VM) (e.g., the Java Virtual Machine or JVM).
●​ Advantage: Combines the speed benefits of compilation (bytecode is faster than pure interpretation)
with the portability of an interpreter (the VM abstracts the hardware).
●​ Process: Source Code $\rightarrow$ Compiler $\rightarrow$ Bytecode $\rightarrow$ VM $\rightarrow$
Machine Code (Execution).

5. Security and System Reliability

5.1 Redundancy and Reliability
●​ Reliability: The ability of a system to perform its required functions under stated conditions for a
specified period of time.
●​ Redundancy: The duplication of critical components or functions of a system with the intention of
increasing reliability.
○​ Example: Using RAID (Redundant Array of Independent Disks) to ensure data is not lost if one
disk fails, or having backup power supplies.

5.2 Protection and Security

The OS must provide mechanisms to protect resources and isolate user processes.
●​ Memory Protection: Ensures that one program cannot access or modify the memory space allocated
to another program or the operating system itself.
●​ Access Control/User Permissions: Regulates which users or processes can read, write, or execute
specific files or resources.
●​ Encryption: The process of encoding data so that it can only be decoded and read by authorized
users with a key. This is a primary method for securing stored and transmitted data.

​
You're looking for a detailed revision guide on IBDP Computer Science HL Topic 3: Networks. This topic
covers the technical structure of networks, communication protocols, and the different models used for data
1
transmission.
Here is the expanded guide, structured for depth and clarity.

🌐 IBDP Computer Science HL: Networks

1. Network Fundamentals
2
A network is a group of interconnected computing devices capable of sending and receiving data.
 Concept Definition & Purpose Key Features

Protocol A set of rules governing Defines format, order, and error

communication between devices. handling.
MUST be agreed upon by all
parties.

Bandwidth The amount of data that can be Usually measured in bits per
transmitted over a network second (bps). Higher is better
connection in a given amount of for speed.
time.

Latency The time delay before a transfer Measured in milliseconds (ms).

of data begins following an Lower is better for real-time
instruction for its transfer. applications.

Packet A small unit of data transmitted Contains source/destination

over a network. Data is broken addresses, sequence number,
into packets for efficient routing. and payload (data).

2. Network Types and Topologies

2.1 Network Scope

Type Scope Example Key Technology

LAN (Local Small geographic Ethernet (Wired), Wi-Fi Typically privately

Area area (e.g., home, (Wireless). owned and
Network) school, office managed.
building).

WAN (Wide Large geographic The Internet, national Often uses leased
Area area, often telecommunication lines or specialized
Network) connecting multiple links. switching
LANs (e.g., country, hardware.
global).

2.2 Network Topologies

3
Topology refers to the physical or logical arrangement of connections (links and nodes).
 Topology Arrangement Advantage Disadvantage

Star All devices connect to Easy fault Central device failure

a central hub/switch. identification; brings down the
failure of one link whole network.
doesn't affect
others.

Bus All devices connect to Simple, uses less Single point of failure
a single shared cabling. (the bus);
communication line. performance
degrades with heavy
traffic.

Mesh Every device is Highly redundant Very expensive and

connected to every and fault-tolerant; complex to
other device (fully) or good for WANs. implement.
most others (partial).

3. The Internet and Addressing

3.1 IP Addressing and Subnetting
An Internet Protocol (IP) address is a unique numerical label assigned to every device participating in a
4
computer network.

5
●​ IPv4: Uses 32 bits (e.g., [Link]). Limited number of addresses.
6
●​ IPv6: Uses 128 bits (e.g., 2001:db8:0:1:1:1:1:1). Provides a vast number of unique addresses.
●​ Subnet Mask: Used to separate the network portion of an IP address from the host portion, allowing
7
network administrators to segment a large network into smaller, manageable subnets.

3.2 Domain Name System (DNS)

The DNS is a hierarchical, decentralized naming system for computers, services, or any resource connected
8
to the Internet.

●​ Function: Translates human-readable Domain Names (e.g., [Link]) into machine-readable IP

9
Addresses (e.g., [Link]).
●​ Process: When a user enters a URL, the local device sends a request to a DNS server, which
10
recursively queries other servers until it finds the corresponding IP address.

3.3 Network Hardware

 Device Role Function

Router Connects different networks Uses IP addresses to forward packets

(e.g., a home LAN to the ISP's between networks; maintains a routing
WAN). table.

Switch Connects devices within a Uses MAC addresses to send data

single network (LAN). only to the intended recipient
(intelligent traffic control).

Modem Converts digital signals from a Modulation/Demodulation.

computer into analog signals
for transmission over
traditional lines (e.g., cable,
phone line) and vice-versa.

4. The OSI and TCP/IP Models (Protocol Stacks)

Communication across networks is managed by layering protocols, which simplifies design and allows for
11
easier replacement of specific technologies.

4.1 The TCP/IP Model (Internet Standard)

This is the practical model used by the Internet. Data moves down the stack at the sender and up the stack at
12
the receiver.

Layer Protocol Examples Data Unit Key Function

Application HTTP, SMTP, FTP, DNS Message / User interface;

Data networking
applications (Web,
Email).

Transport TCP (reliable, Segment Host-to-host

connection-oriented) communication; error
$\rightarrow$ UDP checking;
(unreliable, segmentation.
connectionless)
 Internet IP (Internet Protocol) Packet / Routing packets
Datagram across networks using
IP addresses.

Network Ethernet, Wi-Fi, ARP Frame Physical data

Access transmission; defining
MAC addresses.

4.2 Key Protocols and Services

Protocol Layer Function

TCP (Transmission Transport Provides reliable, ordered, error-checked

Control Protocol) delivery. Used for web browsing (HTTP) and
email (SMTP).

UDP (User Datagram Transport Provides fast, connectionless, unreliable

Protocol) delivery. Used for real-time data like video
streaming and VoIP.

HTTP (HyperText Application Used for retrieving web pages from servers.
Transfer Protocol)

HTTPS Application Secure version of HTTP; uses TLS/SSL for

encryption.

SMTP (Simple Mail Application Used for sending emails.

Transfer Protocol)

FTP (File Transfer Application Used for transferring files between a client
Protocol) and server.

5. Network Security and Transmission

5.1 Wireless Networking (Wi-Fi)
13
Wi-Fi (IEEE 802.11 standard) uses radio waves to transmit data.
 14
●​ Security: Early Wi-Fi used WEP (Wired Equivalent Privacy), which was easily broken. Current
standards are WPA2 and WPA3, which use advanced encryption algorithms (e.g., AES) to secure
15
data.
●​ Access Point (AP): A device that creates a wireless LAN (WLAN).

5.2 Network Security Measures

16
Security is layered across physical and logical defenses.

Measure Purpose Detail

Firewall Filters incoming and outgoing Can be software or

network traffic based on hardware; often filters by IP
predefined security rules. address, port number, or
protocol.

Encryption Scrambling data to prevent Used by HTTPS, VPNs, and

unauthorized interception and WPA2/3. TLS/SSL is the
reading during transmission. standard protocol.

Authentication Verifying the identity of a user Requires usernames,

or device before granting passwords, or digital
access to the network. certificates.

Proxy Server Acts as an intermediary for Hides the client's identity;

requests from clients seeking filters content; can cache
resources from other servers. frequently accessed pages.

5.3 Communication Methods

17
●​ Simplex: Communication in one direction only (e.g., a broadcast radio).
18
●​ Half-Duplex: Communication in both directions, but only one at a time (e.g., walkie-talkie).
19
●​ Full-Duplex: Communication in both directions simultaneously (e.g., a standard telephone call).

I understand you need the next detailed section for your IBDP HL revision guide, focusing on System
Fundamentals that was not covered in the previous, more hardware/OS-centric response.

This section will detail Digital Logic and Data Representation, which forms the most fundamental layer of
computer science, often covered under the umbrella of System Fundamentals.
🔢 IBDP Computer Science HL: Digital Logic and
Data Representation
1. Data Representation: Bits and Encoding
All data in a computer system is stored in a binary format (0s and 1s).

Concept Definition Size

Bit (Binary The smallest unit of data; a 0 or a 1. 1 bit

Digit)

Nibble Half a byte. 4 bits

Byte Standard grouping of bits. 8 bits

Word The number of bits a CPU processes Varies (e.g., 4

simultaneously (e.g., 32-bit or 64-bit word). or 8 bytes)

1.1 Number Systems

Computer science requires understanding how to convert between bases.

Base Name Digits Used Example

2 Binary 0, 1 $1011_2$

10 Denary (Decimal) 0 to 9 $11_{10}$

16 Hexadecimal 0 to 9, A to F $B_H$ or $B_{16}$

Conversion Principle: Each position in a number system represents a power of the base.

Example: Binary to Denary Conversion

10112​

1×23+0×22+1×21+1×20
8+0+2+1=1110​

Hexadecimal Use: Hex is a compact way to represent large binary strings (e.g., memory addresses or
colors). A single hex digit represents 4 binary bits (a nibble).
●​ $11_{10}$ in Hex is $B_{16}$ ($B$ represents $11$).

1.2 Character Encoding

Since computers only store numbers, character sets are used to map a numerical value to a specific character.

Encoding System Size Max Key Use

(Bits) Characters

ASCII (American 7 or 8 128 (7-bit) or Used for basic English letters,

Standard Code for 256 (8-bit) numbers, and symbols.
Information
Interchange)

Unicode 16, 32, Over 1 million Global standard; supports all

or more world languages, emojis, and
specialized symbols (e.g., UTF-8
is a common variable-length
implementation).

1.3 Representing Negative Numbers (Two's Complement)

The standard method for representing negative integers is Two's Complement. It allows for subtraction to be
treated as addition, simplifying the ALU design.

Steps to find the Two's Complement of a negative number (e.g., $-5$ in 8-bit):
1.​ Find the Binary of the positive number ($+5_{10} = 00000101_2$).
2.​ Invert the Bits (One's Complement): Flip all 0s to 1s and 1s to 0s ($11111010_2$).
3.​ Add 1 to the inverted result ($11111010_2 + 1_2 = 11111011_2$).
4.​ The result $11111011_2$ represents $-5_{10}$.
○​ Sign Bit: The Most Significant Bit (MSB, leftmost bit) is 1 for negative numbers.

Representation 8-bit Range

Unsigned Integer $0$ to $255$

 Two's Complement $-128$ to $127$

1.4 Representing Real Numbers (Floating Point)

Real numbers (numbers with a fractional part) are stored using Floating Point representation, based on
scientific notation.

Component Function

Sign (S) Indicates positive (0) or negative (1).

Mantissa (M) Stores the significant digits of the number.

Exponent (E) Stores the power of 2 by which the mantissa is multiplied;

determines the position of the binary point.

Formula: $N = S \times M \times 2^E$

●​ Trade-off: Increasing the size of the Exponent increases the Range (largest/smallest number).
Increasing the size of the Mantissa increases the Precision (number of significant digits).
●​ Error: Floating point arithmetic can lead to Round-off Errors due to the finite space available for the
mantissa.

2. Digital Logic: Gates and Circuits

Digital logic forms the physical basis of the CPU's ALU and Control Unit.

2.1 Logic Gates

Logic gates take one or more binary inputs and produce a single binary output.

Gate Symbol Truth Table (A, B → Boolean Expression Function

Q)

AND

| 0, 0 → 0; 1, 1 → 1 | Q=A⋅B | Output is 1 only if ALL inputs are 1. |

| OR |Shutterstock

| 0, 0 → 0; 1, 0 → 1 | Q=A+B | Output is 1 if ANY input is 1. |

| NOT |Getty Images

| 1 → 0; 0 → 1 | Q=A | Inverts the input. |

| XOR (Exclusive OR) |Shutterstock

| 0, 0 → 0; 1, 0 → 1 | Q=A⊕B | Output is 1 if inputs are DIFFERENT. |

NAND and NOR Gates: These are considered Universal Gates because any other gate (AND, OR, NOT)
can be constructed using only one of them.

2.2 Logic Circuits (Boolean Algebra)

Logic circuits implement complex functions by combining gates.
●​ Truth Table: Defines the output of a circuit for every possible combination of inputs.
●​ Boolean Expression: A mathematical expression describing the circuit's logic (e.g., $Q = \overline{A}
\cdot (B + C)$).

Example: Constructing an Adder Circuit

●​ Half Adder: A circuit that adds two single-bit binary numbers ($A$ and $B$).
○​ Sum Output: $S = A \oplus B$ (XOR gate)
○​ Carry Output: $C = A \cdot B$ (AND gate)
●​ Full Adder: A circuit that adds three single-bit inputs ($A$, $B$, and a Carry-In from a previous stage)
to produce a Sum and a Carry-Out.

A sequence of Full Adders forms a Ripple-Carry Adder, which the ALU uses to perform addition.

3. Exam-Focused Summary: Data Fundamentals

Concept Key Point Exam Focus Tip

Two's Used for signed integers. MSB = Construct the 8-bit/16-bit

Complement 1 means negative. representation of a negative
number.

Floating Point Used for real numbers. Trade-off Explain the limitations of
between Range (Exponent) finite precision (round-off
and Precision (Mantissa). error).

Logic Gates The building blocks of the CPU. Construct a Truth Table for a
NAND and NOR are Universal. given Boolean Expression or
circuit.

FDE Cycle Driven by the Control Unit and Describe the exact role of
registers (PC, MAR, MDR, IR). the PC (stores address of
next instruction).