IBDP Computer Science B2.3 Programming constructs HL Paper 1 - New Syllabus

Question

A two-dimensional array is also known as a matrix.

A square matrix is a matrix with the same number of rows and columns.

Figure $1$: Example data stored in four square matrices: AMAT, BMAT, CMAT, and DMAT

AMAT

	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
$[0]$	$2$	$4$	$1$	$4$	$5$
$[1]$	$0$	$5$	$7$	$0$	$6$
$[2]$	$0$	$0$	$3$	$2$	$2$
$[3]$	$0$	$0$	$0$	$2$	$3$
$[4]$	$0$	$0$	$0$	$0$	$9$

BMAT

	$[0]$	$[1]$	$[2]$	$[3]$
$[0]$	$1$	$0$	$0$	$0$
$[1]$	$3$	$6$	$0$	$0$
$[2]$	$4$	$0$	$7$	$0$
$[3]$	$0$	$3$	$2$	$0$

CMAT

	$[0]$	$[1]$	$[2]$
$[0]$	$2$	$0$	$0$
$[1]$	$0$	$5$	$0$
$[2]$	$0$	$0$	$3$

DMAT

	$[0]$	$[1]$	$[2]$	$[3]$
$[0]$	$1$	$5$	$0$	$0$
$[1]$	$3$	$6$	$9$	$0$
$[2]$	$4$	$0$	$7$	$1$
$[3]$	$0$	$3$	$2$	$0$

The main diagonal is the set of elements that run from the upper left-hand corner of the matrix to the lower right-hand corner of the matrix.

(a) State all the main diagonal elements in the matrix DMAT in Figure $1$. $[1]$

(b) Describe the process to check whether an element of a matrix is a main diagonal element. $[2]$

In an upper triangular matrix, all entries below the main diagonal are $0$.

The sub-program isUpper(MAT,N) accepts a square matrix MAT and an integer N that represents the number of rows and columns.

It returns TRUE if MAT is an upper triangular matrix; otherwise it returns FALSE.

For example, from Figure $1$:

isUpper(AMAT,$5$) returns TRUE
isUpper(CMAT,$3$) returns TRUE
isUpper(DMAT,$4$) returns FALSE
isUpper(BMAT,$4$) returns FALSE

(c) Construct an algorithm in pseudocode for the sub-program isUpper(MAT,N) as described. $[7]$

In a lower triangular matrix, all entries above the main diagonal are $0$.

The sub-program isLower(MAT,N) accepts a square matrix MAT and an integer N that represents the number of rows and columns.

It returns TRUE if MAT is a lower triangular matrix; otherwise it returns FALSE.

For example, from Figure $1$:

isLower(AMAT,$5$) returns FALSE
isLower(CMAT,$3$) returns TRUE

The sub-program identify(MAT,N) calls sub-programs isLower(MAT,N) and isUpper(MAT,N) to determine and output whether the square matrix MAT is:

• upper triangular;
• lower triangular;
• both upper and lower triangular;
• none of the above.

For example, from Figure $1$:

identify(AMAT,$5$) outputs ‘UPPER’
identify(BMAT,$4$) outputs ‘LOWER’
identify(CMAT,$3$) outputs ‘BOTH’
identify(DMAT,$4$) outputs ‘NONE’

(d) Construct an algorithm in pseudocode for the sub-program identify(MAT,N) as described. $[5]$

Most-appropriate topic codes (CED):

• TOPIC B2.2: Data structures — parts (a) and (b)
• TOPIC B2.3: Programming constructs — parts (c) and (d)

▶️ Answer/Explanation

Detailed solution

(a)
The main diagonal consists of elements whose row and column positions are the same.

For DMAT, these are:

$\boxed{1,\ 6,\ 7,\ 0}$

Answer: $1,\ 6,\ 7,\ 0$.

(b)
Compare the row index and column index of the matrix element.

• If the row index is equal to the column index, the element lies on the main diagonal.
• If the row index is not equal to the column index, the element is not on the main diagonal.

In index notation, an element MAT$[i][j]$ is on the main diagonal when:

$\boxed{i=j}$

(c)
For an upper triangular matrix, every element below the main diagonal must equal $0$. An element is below the diagonal when its row index is greater than its column index.

A suitable pseudocode algorithm is:

isUpper(MAT,N)
loop ROW from $1$ to $N-1$
loop COL from $0$ to $ROW-1$
if MAT[ROW][COL] $\ne 0$
then return FALSE
end if
end loop
end loop
return TRUE
end isUpper

The outer loop starts at row $1$ because row $0$ has no elements below the main diagonal. For each row, the inner loop checks only columns from $0$ to $ROW-1$, which are precisely the positions below the diagonal.

If any one of these elements is non-zero, the matrix cannot be upper triangular, so the function immediately returns FALSE. If all required positions contain $0$, it returns TRUE.

(d)
The sub-program can call isUpper(MAT,N) and isLower(MAT,N) once each and store their Boolean results.

identify(MAT,N)
A = isUpper(MAT,N)
B = isLower(MAT,N)
 
if A and B
then output(‘BOTH’)
else if A and not B
then output(‘UPPER’)
else if not A and B
then output(‘LOWER’)
else
output(‘NONE’)
end if
end identify

The two Boolean values give the four possible cases:

• A = TRUE and B = TRUE → BOTH;
• A = TRUE and B = FALSE → UPPER;
• A = FALSE and B = TRUE → LOWER;
• both are FALSE → NONE.

This avoids repeating the calls to the two checking sub-programs and makes the decision structure straightforward.

IBDP Computer Science B2.3 Programming constructs HL Paper 1 - New Syllabus

Question

Resources

Members

Company