IB Questionbank

User interface language: English | Español

Date	November 2020	Marks available	3	Reference code	20N.1.HL.TZ0.13
Level	HL	Paper	1	Time zone	no time zone
Command term	Construct	Question number	13	Adapted from	N/A

Question

Images in computers are stored as two-dimensional arrays.

A black-and-white image (Figure 1) is stored as a 10 × 10 two-dimensional array named MAT (Figure 2).

Each element of MAT holds a number for a colour; 1 represents the colour black and 0 represents the colour white.

In an application, the black-and-white image can be inverted (all white pixels are changed to black, and all black pixels are changed to white).

Method invert(N,A) accepts a positive integer N and an N × N two-dimensional array A that holds the data for a simple black-and-white image; it returns the inverted N × N two-dimensional array A.

In the application, it is also possible to rotate an image clockwise by 90 degrees (90°).
For example, when the simple black-and-white image is rotated, the corresponding 10 × 10 two-dimensional array MAT is updated.

This would mean the first row of the original MAT is the last column in the rotated MAT, the second row is the second-to-last last column, … and the last row is the first column.

Consider the following algorithm fragment:

K=input()
loop for M=0 to K mod 4 - 1
    A=rotate(N,A)
end loop

where:

N is an integer and A is the N × N two-dimensional array that holds data about an image
K(K>=0) is an integer showing how many times the image should be rotated
method rotate(N,A) accepts an integer N and an N × N two-dimensional array A representing an image. It returns an N × N two-dimensional array representing the image rotated clockwise by 90°.

The algorithm for method rotate(N,A) uses an additional N × N two-dimensional array, named The N × N dimensional array B is initialized and updated using the values from A to represent the image rotated clockwise by 90°.

Construct an algorithm in pseudocode for the method invert(N,A).

[3]

State the number of degrees by which the image will be rotated if the input value of K is 3.

[1]

b.i.

Outline why it is more efficient that the loop in the given algorithm fragment executes (K mod 4) times instead of K times. You may give an appropriate example in your answer.

[2]

b.ii.

Construct the algorithm in pseudocode for the method rotate(N,A) described above.

[3]

To avoid inefficient use of memory, a new algorithm for the method rotate(N,A) is constructed.

The N × N two-dimensional array A should be rotated clockwise by 90°, without the use of any additional arrays.

One way of rotating the two-dimensional array A clockwise by 90° is to transpose A, and then reverse each row of A.

The transpose of A is formed by turning all the rows of A into columns. For example, the value in the first row and third column (A[1][3]) is swapped with the value in the third row and first column (A[3][1]).

Construct the new algorithm in pseudocode for the method rotate(N,A) described above.

[6]

Markscheme

Award [3 max]
Award [1] for nested loops/loop through all array elements;
Award [1] for checking the array element for the number of colour;
Award [1] for updating correctly each of the array elements;

Example 1:

loop for I=0 to N-1
    loop for J=0 to N-1
        if A[I][J]==1
            then A[I][J]=0
            else A[I][J]=1
        end if
    end loop
end loop

Example 2:

R=0
C=0
I=0
loop while I< N*N
    if A[R][C]==0
        then A[R][C]=1
        else A[R][C]=0
    end if
    C=C+1
    if C>9 then
        C=0
        R=R+1
    end if
    I=I+1
end loop

Award [1 max]
270 (degrees);

b.i.

Award [2 max]
A rotation by 360 degrees returns the image/matrix to its original value, so no action need be taken. A rotation by 360+N degrees is equivalent to a rotation by N degrees(this logic repeats, so for 90 degree rotations, there are only 3 transformations needed: by 90, by 2*90 and by 3*90);
making more is unnecessary/inefficient;

Unnecessary calls to the method rotate() which would make the algorithm less efficient are avoided;
for example, repeating 10 times and repeating 2 (=10 mod 4) times, both return the array holding the image rotated by 180 degrees;

NOTE: Accept any appropriate example, with any value of K which is greater than or equal to 4;

b.ii.

Award [3 max]
Award [1] for completely correct nested loops;
Award [1] for correctly determining row indexes (in both matrixes, A and B);
Award [1] for correctly determining column indexes (in both matrixes, A and B);

NOTE: The method heading and return statement may not appear in the answers. Only an algorithm for the method rotate() is requested.

Example:

rotate(N,A)
    // initialize two dimensional array B
    // for example, int[][] B = new int[N][N];

      loop for I = 0 to N-1
            loop for J = 0 to N-1
                 B[I][J] = A[N-J–1][I]
                    // instead of these array subscripts
                    // the following can be written
                    // B[J][N-1-I] = A[I][J]
             end loop
       end loop

       return B
end rotate

Award [6 max]

Example:
(Transposes the two-dimensional array and then reverses each row.)

Award [3] for transposing.
Award [1] for the correct outer loop;
Award [1] for the correct inner loop;
Award [1] for the correct swap;

Award [3] for reversing each row of the transposed matrix.
Award [1] for the correct outer loop;
Award [1] for the correct inner loop;
Award [1] for the correct swap;
Award [1] for using nothing but a temporary variable to achieve this / no additional / extra space used except one temporary variable;

NOTE: The method heading and return statement may not appear. Only the algorithm for the method rotate() is requested.

rotate (N,A)
                       //transposes A
     loop for I=0 to N-1
          loop for J=0 to I-1 
             TEMP = A[I][J]
             A[I][J] = A[J][I] 
             A[J][I] = TEMP
          end loop
     end loop
                     // reverses each row of transposed matrix A
     loop for I=0 to N-1
          loop for J=0 to N div 2-1
             TEMP = A[I][J]
             A[I][J] = A[J][I]
             A[J][I] = TEMP
          end loop
     end loop
     return A
end rotate

Examiners report

This was answered well.

The question was well answered with many gaining full marks.

b.i.

The question was well answered with many gaining full marks.

b.ii.

Answers to this question vary from poor to excellent. Some candidates constructed excellent algorithms and they gained full marks on this question.

Syllabus sections

Topic 5: Abstract data structures » 5.1 Abstract data structures

Show 80 related questions

17N.1.HL.TZ0.13c:

Show the output produced by the following algorithm.

loop while (NOT FRUITS.isEmpty()) AND (NOT FLOWERS.isEmpty())
  X = FRUITS.pop()
  Y = FLOWERS.pop()
  if X < Y then
    output X
  else
    output Y
  end if
end loop

Hide related questions

Topic 5: Abstract data structures

Question

Markscheme

Examiners report

Syllabus sections

View options