1.

(a) The following algorithm ALG1 processes an integer array X with indices
from 1 to n.

ALG1
Step 1: for i from 1 to n-1 do steps 2 to 6
Step 2: for j from 1 to n- 1 do steps 3 to 6
Step 3: if x [j] > [j+1] then do steps 4 to 6
Step 4: k  X [j] + X[j+1]
Step 5: X [j]  k- X [j]
Step 6: X [j+1]  k-X [j]

(i) Suppose n = 6. The initial content of X is shown below. Dry run

ALG1 .
X[1] X[2] X[3] X[4] X[5] X[6]
5 6 2 3 1 4

(1) Fill in the content of X after the first pass and second pass of the
loop in Step 1.
After first pass
X[1] X[2] X[3] X[4] X[5] X[6]

After second pass

X[1] X[2] X[3] X[4] X[5] X[6]

(2) Fill in the final content of X.

X[1] X[2] X[3] X[4] X[5] X[6]

(3) How many times will the statement in Step 3 be

executed?
(ii) It is suggested that changing Step 2 to ‘for j from l to n-i do
Steps 3 to 6’ can improve the algorithm. Do you agree† Justify your
answer.
 (iii) Suppose only the second largest value in X should be calculated and
output.

(1) Which entry should be output after executing ALG1? X[ ]

(2) Modify Step 1 so that the times of execution of Step 3 can be

minimized.

for i from to do Steps 2 to 6

(9 marks)

(b) The following algorithm ALG2 processes P and Q, which are integer arrays
with indices from 1 to n. The integers in the arrays are sorted in descending
order. X is an integer array with indices from 1 to(n+n).

ALG2
Step 1: i  n ; j  n ; k  1
Step 2: while k <=(n+n ) do steps 3 to 10
Step 3: if j=0
Step 4: then X[k]  P[i] and i  i - 1
Step 5: else if i=0
Step 6: then X[k]  Q[j] and j  j - l
Step 7: else if P[i] < Q [j]
Step 8: then X [k]  P [i] and i  i - l
Step 9: else X [k]  Q[j] and j  j - 1
Step 10: k  k + 1

Suppose n = 6. The initial contents of P and Q are shown below. Dry

run ALG2.
P[1] P[2] P[3] P[4] P[5] P[6]
12 10 9 6 2 1
Q[1] Q[2] Q[3] Q[4] Q[5] Q[6]
11 8 7 5 4 3
 (i) What are the final contents of X[1] and X[12]?

X[1] X[12]

(ii) How many times will the statement in Step 3 be

executed?

(iii) Simplify Steps 3 to 9 in one single ‘if-then-else’ statement.

(6 marks)
2. The algorithm CAL processes the operation of an arithmetic expression stored in
an array N. N contains integers and symbols ‘ (‘ , ’) ’, ‘ +’ and ‘ -’. CAL makes
use of the following operations on the stack S:

push(K, S) puts the element K on the top of S

pop(S) removes and returns the element from the top of S

CAL
Step 1: Initialise S to empty
Step 2: i  1
Step 3: while N[i] is nor empty do Steps 4 to 12
Step 4: if N[i] = ‘ )’ then do steps 5 to 10
Step 5: A  pop(S)
Step 6: B  pop(S)
Step 7: C  pop(S)
Step 8: temp  pop(S)
Step 9: If B = ‘ +’ then push(C + A, S)
Step 10: else push(C - A, S)
Step 11: else push(N[i],S)
Step 12: i  i + 1
Step 13: Output pop(S)

(b) Choose four statements from the following statements ① to ⑥ complete

the flowchart of GAL below.

① The symbol is ‘ +’?

② Insert the symbol to S
③ N[i] is empty?
④ Do the arithmetic and insert the result in S
⑤ N[i] = ‘ )’?
⑥ Remove an element from S
 (4 marks)

(c) The initial content o N is given below.

N[1] N[2] N[3] N[4] N[5] N[6] N[7] N[8] N[9] N[10
]
( ( 2 + 3 ) - 4 )

Dry run CAL and write the content of S below.

In Step 12,
when i is changed from 5 to 6 when i is changed from 5 to 6

 Bottom of S  Bottom of S
 (d) Suppose that S is implemented by an array, the content of N is valid and the
size of N is 10. What is the minimum size of S?

(e) The following three sets of test cases will be used for testing CAL.
Test case N[1] N[2] N[3] N[4] N[5] N[6] N[7] N[8] N[9]
A1 ( 1 + 2 )
Set A ( 1 - 2 )
A2
A3 ( ( l - 2 ) + 3 )

Test case N[1] N[2] N[3] N[4] N[5] N[6] N[7] N[8] N[9]
B1 1 + 2 )
Set B 1 1 + 2 ) )
B2
B3 ( 1 + 2 ) + 3

Test case N[1] N[2] N[3] N[4] N[5] N[6] N[7] N[8] N[9]
Set C Cl
C2 1

State the different uses of the three sets of test cases.

Set A:

Set B:

Set C:

(3 marks)
3. Mr Li works on a project to develop an online auction system. Users can submit
auction item information to create an auction entry or bid an auction item
through the system.

(d) Given that myRAND is a subprogram which randomly returns an integer

between 1 and 1000 inclusively, Mr Li designs the following algorithm R1 to
randomly select one auction item.

R1
Step 1: n  number of auction items

Step 2: i  remainder of (myRAND() ÷ n) + 1

Step 3: return the i-th item

(i) Write myRAND in Pascal, C, Visual Basic or Java so that the computer
will return different random numbers every time myRAND is executed.

(ii) Mr Li find that some auction items could never be selected by R1. What
would the total number of auction items be?

(iii) Mr Li finds that some auction items could be selected more often than
the others by R1. What would the total number of auction items be?

(5 marks)
4. Mary uses a software package to store some black and white images of 4x4
pixels as text files. The software package has Method l and Method 2 to store the
images, as described below. In both methods, ‘1’ and ‘0’ represent a black pixel and
a white pixel respectively.

Method 1: An image is stored as a text file containing 4x4 characters of I's and
‘0’s. Each pixel of the image is represented by the corresponding character in the
file.

Method 2: An image is scanned from the top row, left to right. Sets of two
numbers (P, Q) in the text file are used to represent the pixels where P is the digit 1
or ‘0’ (black/white pixel) and Q is the number of consecutive digits.

Example 1 shows how the software package stores an image.

(a) An image is stored by Method 2, as shown below. Shade the black pixels of the image
on the right hand side.

(2 marks)

(b) (i) With respect to file size, describe a best case and a worse case of images stored by
Method 2.
Best case:

Worst case:
 (iii) Other than file size, give an advantage of Method 1 over Method 2.

(c) An image is saved as a text file using Method 1 and the data in the text file is stored in a
global two-dimensional array BD. The array items of BD with the indices (1, 1) and (4,
4) store the digits in the top left hand corner and the bottom right hand corner respectively.

Mary wants to write a subprogram ENC to save the image as a text file using Method 2 with BD
using the following variables for storing the data in the text file.

Variable Description
P A global integer array for storing the first value in each set of (P, Q)
Q A global integer array for storing the second values in each set of (P, Q)

In Example 1

Pascal / C / Java versions Visual Basic version

P[1] = 1, Q[1] = 3 P(1) = 1, Q(1) = 3
P[2] = 0, Q[2] = 5 P(2) = 0, Q(2) = 5
P[3] = 1, Q[3] = 8 P(3) = 1, Q(3) = 8
 (i) Complete ENC.

[Pascal version]
procedure ENC;
var
i, j, k, current integer;
begin
k :=1;
p[1] := BD[1,1];

; Q[1] :=
; Current :=

for i := 1 to 4 do
for j := 1 to 4 do
if ) (BD[I,j] =
then

Q[k] := Q[k] +
else begin
k := k + 1
P[k] := BD[i,j];

Q[k] :=

Current := BD[i,j];
end;
end;

(ii) Mary wants to reduce the memory usage of ENC. She thinks that it can be rewritten
such that only the first element in P is required. In other words, the other elements
in P are not required. Do you agree? Explain briefly.

(7 marks)