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

1 Information Representation Refresher

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

  DEC  =  45
  BIN  =  0010 1101
  HEX  =  2D
  

  Conversion rule: address = baseaddress + index × wordsize (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 = baseaddress + i × wordsize

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

address = baseaddress + (row × COLS + col) × wordsize

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.

Visualising a 2‑D Array

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.