Write pseudocode for 1D and 2D arrays

Topic 10.2 – Arrays (Cambridge AS & A‑Level Computer Science)

Objective

Write clear, correct pseudocode for declaring, initialising, accessing and processing one‑dimensional (1‑D) and two‑dimensional (2‑D) arrays. Relate arrays to data types, records, abstract data types (ADTs), testing, and to the broader Cambridge syllabus topics on representation, hardware, communication and system software.

Prerequisite Knowledge

• Basic data types: INTEGER, REAL, CHAR, BOOLEAN.
• Constants and simple variables.
• Control structures – FOR loops and IF statements.
• Familiarity with the syllabus structure (10.1 Data Types & Records, 10.2 Arrays, 10.4 ADTs, 12 Testing).

Syllabus Context – How Arrays Fit In

Syllabus Block	Relevance to Arrays
1 Information representation	Arrays store binary data; character arrays rely on ASCII/Unicode codes; compression can be applied to large arrays.
2 Communication	Arrays are often transmitted over networks (e.g., sending a sensor data buffer).
3 Hardware	Contiguous memory layout, address calculation, registers and bus transfers.
4 Processor fundamentals	Bit‑wise operations for packing/unpacking values in arrays.
5 System software	File I/O for persisting arrays; OS services for memory allocation.

1 Information Representation Refresher

• Binary ↔ Decimal ↔ Hexadecimal – useful when calculating memory addresses.

  DEC  =  45
  BIN  =  0010 1101
  HEX  =  2D
          

  Conversion rule: address = base_address + index × word_size (see “Memory layout” below).

• Character encodings – each CHAR occupies one byte (ASCII 0‑127) or more (Unicode). When declaring a CHAR array, remember that each element stores the numeric code point.
• Lossless compression (run‑length encoding) – a simple technique for arrays with repeated values:

  INPUT  : 5 5 5 2 2 9 9 9 9
  OUTPUT : (5,3) (2,2) (9,4)   // value, count pairs
          

  Use when the question asks to “compress an array before transmission”.

2 Hardware – Memory Layout & Address Calculation

Arrays occupy a contiguous block of memory. The address of element A[i] is:

address = base_address + i × word_size

For a 2‑D array M[ROWS][COLS] stored row‑major:

address = base_address + (row × COLS + col) × word_size

Example	Base address	Word size	Index calculation
scores[5]	0x1000	4 bytes (INTEGER)	address(scores[i]) = 0x1000 + i×4
matrix[3][4]	0x2000	4 bytes	address(matrix[r][c]) = 0x2000 + (r×4 + c)×4

3 Processor Fundamentals – Bit‑wise Array Tricks

• Pack two 8‑bit values into one 16‑bit integer:

  packed ← (highByte << 8) OR lowByte
          

• Extract the original bytes:

  highByte ← (packed >> 8) AND 0xFF
  lowByte  ← packed AND 0xFF
          

• These techniques are useful when an array must store more than one logical value per memory word (e.g., image pixels).

4 Communication – Transmitting Arrays

When an array is sent over a network the following steps are typical:

1. Serialise the array (convert to a byte stream). For numeric arrays this is usually a simple copy of the binary representation; for character arrays ensure the same encoding (ASCII/UTF‑8).
2. Add a length field so the receiver knows how many elements to read.
3. Transmit using a reliable protocol (TCP) or an unreliable one (UDP) depending on the application.

5 System Software – File I/O with Arrays

PROCEDURE writeArrayToFile(arr, size, filename)
    OPEN file FOR WRITE AS f
    WRITE f, size               // first write the length
    FOR i FROM 0 TO size‑1
        WRITE f, arr[i]
    END FOR
    CLOSE f
END PROCEDURE

PROCEDURE readArrayFromFile(filename) RETURNS (array, size)
    OPEN file FOR READ AS f
    READ f, size
    DECLARE array[size] AS INTEGER
    FOR i FROM 0 TO size‑1
        READ f, array[i]
    END FOR
    CLOSE f
    RETURN (array, size)
END PROCEDURE

These procedures illustrate the OS service (file handling) that underpins persistent storage of arrays.

Key Concepts

• Array definition: a contiguous block of memory holding a fixed number of elements of the same type.
• Indexing convention: most languages use 0‑based indexing; some (e.g., Visual Basic) use 1‑based. Adjust loop bounds accordingly.
• Dimensions: 1‑D = single row; 2‑D = table of rows × columns (matrix).
• Size constants: always use named constants (no “magic numbers”).
• Bounds checking: valid indices satisfy 0 ≤ index < size. Accessing outside this range causes a run‑time error.
• Common operations: initialise, assign, retrieve, search, sort, compute aggregates (sum, average), transpose, and use arrays to implement ADTs such as stacks and queues.

Declaration, Initialisation & Constants

CONST N    ← 5                     // size of a 1‑D array
CONST ROWS← 3                     // rows in a 2‑D array
CONST COLS← 4                     // columns in a 2‑D array

DECLARE scores[N] AS INTEGER      // 1‑D array
FOR i FROM 0 TO N‑1
    scores[i] ← 0                 // initialise all elements to 0
END FOR

DECLARE matrix[ROWS][COLS] AS INTEGER   // 2‑D array
FOR row FROM 0 TO ROWS‑1
    FOR col FROM 0 TO COLS‑1
        matrix[row][col] ← 0
    END FOR
END FOR

Assigning Values

scores[0] ← 85
scores[1] ← 92
scores[2] ← 78
scores[3] ← 90
scores[4] ← 88

matrix[0][0] ← 1   matrix[0][1] ← 2   matrix[0][2] ← 3   matrix[0][3] ← 4
matrix[1][0] ← 5   matrix[1][1] ← 6   matrix[1][2] ← 7   matrix[1][3] ← 8
matrix[2][0] ← 9   matrix[2][1] ←10   matrix[2][2] ←11   matrix[2][3] ←12

Accessing Elements

PRINT "Score at index 2: ", scores[2]
PRINT "Element at (row 1, col 2): ", matrix[1][2]

Iterating Over Arrays – Common Patterns

1‑D – Compute Sum and Average

sum ← 0
FOR i FROM 0 TO N‑1
    sum ← sum + scores[i]
END FOR
average ← sum / N
PRINT "Total =", sum, "Average =", average

2‑D – Row‑wise Averages

FOR row FROM 0 TO ROWS‑1
    sum ← 0
    FOR col FROM 0 TO COLS‑1
        sum ← sum + matrix[row][col]
    END FOR
    rowAvg ← sum / COLS
    PRINT "Average of row ", row, ": ", rowAvg
END FOR

2‑D – Transpose a Square Matrix (3 × 3 example)

DECLARE temp AS INTEGER
FOR i FROM 0 TO 2
    FOR j FROM i+1 TO 2
        temp ← matrix[i][j]
        matrix[i][j] ← matrix[j][i]
        matrix[j][i] ← temp
    END FOR
END FOR

Conditional Processing Inside a Loop (count values > threshold)

CONST THRESHOLD ← 80
count ← 0
FOR i FROM 0 TO N‑1
    IF scores[i] > THRESHOLD THEN
        count ← count + 1
    END IF
END FOR
PRINT "Number of scores > ", THRESHOLD, ": ", count

Common Algorithms on Arrays

• Linear search – find the first occurrence of a target value.
• Bubble sort – simple O(n²) sorting algorithm suitable for small arrays.
• Bounds checking – always verify 0 ≤ index < size before accessing.

Linear Search (1‑D)

DECLARE target AS INTEGER
READ target
found ← FALSE
FOR i FROM 0 TO N‑1
    IF scores[i] = target THEN
        PRINT "Target found at index ", i
        found ← TRUE
        EXIT FOR
    END IF
END FOR
IF NOT found THEN
    PRINT "Target not in array."
END IF

Bubble Sort (1‑D)

FOR pass FROM 1 TO N‑1
    FOR i FROM 0 TO N‑pass‑1
        IF scores[i] > scores[i+1] THEN
            // swap
            temp ← scores[i]
            scores[i] ← scores[i+1]
            scores[i+1] ← temp
        END IF
    END FOR
END FOR
PRINT "Array sorted in ascending order."

Arrays and Abstract Data Types (ADTs)

Stack (LIFO) using a 1‑D array

CONST MAX ← 10
DECLARE stack[MAX] AS INTEGER
top ← -1                     // empty stack

PROCEDURE push(value)
    IF top = MAX‑1 THEN
        PRINT "Stack overflow"
    ELSE
        top ← top + 1
        stack[top] ← value
    END IF
END PROCEDURE

PROCEDURE pop() RETURNS INTEGER
    IF top = -1 THEN
        PRINT "Stack underflow"
        RETURN NULL
    ELSE
        value ← stack[top]
        top ← top - 1
        RETURN value
    END IF
END PROCEDURE

Queue (FIFO) using a 1‑D array

CONST MAX ← 10
DECLARE queue[MAX] AS INTEGER
front ← 0
rear  ← -1
size  ← 0

PROCEDURE enqueue(value)
    IF size = MAX THEN
        PRINT "Queue full"
    ELSE
        rear ← (rear + 1) MOD MAX
        queue[rear] ← value
        size ← size + 1
    END IF
END PROCEDURE

PROCEDURE dequeue() RETURNS INTEGER
    IF size = 0 THEN
        PRINT "Queue empty"
        RETURN NULL
    ELSE
        value ← queue[front]
        front ← (front + 1) MOD MAX
        size ← size - 1
        RETURN value
    END IF
END PROCEDURE

Arrays of Records (Link to Syllabus 10.1)

DECLARE TYPE StudentRecord
    name AS STRING(20)
    age  AS INTEGER
    mark AS INTEGER
END TYPE

CONST STUDENTS ← 3
DECLARE class[STUDENTS] AS StudentRecord

// initialise
FOR i FROM 0 TO STUDENTS‑1
    class[i].name ← ""
    class[i].age  ← 0
    class[i].mark ← 0
END FOR

Testing & Dry‑Run (Syllabus 12)

Always perform a dry‑run with a small data set before coding. The table below shows a step‑by‑step trace of the “Row‑wise average” algorithm for the 3 × 4 matrix defined earlier.

Step	row	col	sum (so far)	rowAvg (after inner loop)
1	0	0	1
2	0	1	3
3	0	2	6
4	0	3	10	10/4 = 2.5
5	1	0	5
6	1	1	11
7	1	2	18
8	1	3	26	26/4 = 6.5
9	2	0	9
10	2	1	19
11	2	2	30
12	2	3	42	42/4 = 10.5

Visualising a 2‑D Array

Row \ Col	0	1	2	3
0	1	2	3	4
1	5	6	7	8
2	9	10	11	12

Mathematical Notation

• 1‑D array of length n: element at index i is A[i], where 0 ≤ i < n.
• 2‑D array with r rows and c columns: element at row i, column j is M[i][j], where 0 ≤ i < r and 0 ≤ j < c.

Common Pitfalls & How to Avoid Them

• Off‑by‑one errors: Remember the last valid index is size‑1. Use constants and loop to size‑1.
• Wrong indexing convention: Switch loop bounds if you are using a 1‑based language.
• Row/column mix‑up: Always write array[row][col] for 2‑D arrays; never swap unintentionally.
• Missing bounds check: Insert an IF 0 ≤ i < size THEN … END IF before any access, or comment “// assume i is in range”.
• Magic numbers: Replace literals with named constants (e.g., CONST N ← 5).

Practice Questions

1. Write pseudocode to find the maximum value in a 1‑D array of size 10. Include bounds checking.
2. Write pseudocode to transpose a 3 × 3 matrix.
3. Given a 2‑D array M[ROWS][COLS], write pseudocode to calculate the sum of all elements.
4. Implement a stack using a 1‑D array of size 8; provide push and pop procedures with overflow/underflow handling.
5. Perform a dry‑run of the linear‑search algorithm on the array {85, 92, 78, 90, 88} searching for 90. Show the values of the loop variable and the found flag at each step.

Further Reading / What’s Next?

• 10.4 Abstract Data Types: Use arrays to implement stacks, queues, and simple priority queues.
• Dynamic allocation (A‑Level): Create arrays whose size is determined at run‑time.
• File I/O: Storing and retrieving arrays from text or binary files (see Section 5).
• Multi‑dimensional arrays beyond 2‑D (e.g., 3‑D arrays for graphics or scientific data).
• Recursion with arrays: Algorithms such as binary search or recursive matrix multiplication.